数据结构

第一章绪论

常见概念

数据：输入的所有内容
数据元素：数据的基本单位，一条记录
数据项：单条记录中的每个项目

时间复杂度

c

// O(logn)
for (int i=0; i<=n; i*=2)
    k++;

c

// O(m+n)
// O(max(m,n))
for (int i=0; i<=m; i++)
    k++;
for (int i=0; i<=n; i++)
    k++;

c

// O(n^2)
for (int i=0; i<n; i++)
    for (int j=0; j<i; j++)
        k++;
// 频次 n(n+1)/2

空间复杂度（只考虑额外开辟的辅助空间）

c

// O(1)
void BubbleSort(int A[],int n) {
    for (int i=0;i<n-1;i++) {
        bool flag=false;
        for(int j=n-1;j>i;j--)
            ...
    }
}

c

// O(n)
int Func(int n) {
    if (n == 0) return 1;
    return Func(n-1) * n;
}
// 递归栈空间消耗

c

// O(n)
int Fib(int n) {
    if(n < 3) return 1;
	return Fib(n-1) * Fib(n-2);
}
// 递归栈可以重复利用