0、数据结构的学习推荐书籍

（1）《小黑的漫画算法》简单看一下
（2）《大话数据结构》
（3）《数据结构（C语言版）》

1、时间复杂度和空间复杂度

（1）时间复杂度、空间复杂度是什么？

• 算法效率分析分为两种：
  • 第一种是时间效率
  • 第二种是空间效率
• 时间效率被称为时间复杂度，空间效率被称作空间复杂度
• 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间
• 在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度，如今更加考虑时间复杂度

（2）时间复杂度的计算

void Func1(int N)
{int count = 0;for (int i = 0; i < N ; ++ i){for (int j = 0; j < N ; ++ j){++count;}}for (int k = 0; k < 2 * N ; ++ k){++count;}int M = 10;while (M--){++count;}printf("%d\\n", count);
}//实际执行N * N + 2 * N + 10

①代码解析：实际的们计算时间复杂度的时候，不用计算如此精确的执行次数，于是这里我们使用大O渐进表示法。时间复杂度不算时间，算次数

②大O表示法：是用于描述函数渐进行为的数学符号

③推导方法：

• 常数1取代运行时间中的所有加法常数
• 在修改后的运行函数中，只保留最高阶项
• 如果高阶项存在且不是1，则去除于这个项目相乘的常数

④最好、平均、最坏情况：

• 最好情况：任意输入规模的最大运行次数（上界）
• 平均情况：任意输入规模的期望运行次数
• 最好情况：任意输入规模的最小运行次数（下界）

⑤推导例子：

void Func1(int N)
{int count = 0;for (int i = 0; i < N; ++i){for (int j = 0; j < N; ++j){++count;}}for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\\n", count);//仔细分析的话，时间复杂度函数式是F(N)=N^2+2*N+10//但是时间复杂度的重点不是详细的次数，而是给各个函数做一个复杂度分类，因此只需要估算值即可//因此这个函数的时间复杂度就是O(N^2)，是复杂度函数的估算（之所以估算是因为当N足够大时，除了N^2这一项，其他项基本可以忽略不计）
}

void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\\n", count);//该函数的时间复杂函数式是F(N)=2*N+10//故时间复杂度是O(N)
}

void Func3(int N, int M)
{int count = 0;for (int k = 0; k < M; ++k){++count;}for (int k = 0; k < N; ++k){++count;}printf("%d\\n", count);//这个函数的时间复杂度值得思考，注意这里有两个变量，无法确定N和M相对的大小//所以时间复杂度是O(M+N)，而不是简单的O(N)或O(M)，除非给定M和N之间的关系（例如M=N）
}

void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\\n", count);//无论N是多少都对执行次数无关，执行次数是100次，为常数，故时间复杂度为O(1)，代表常数次
}

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}//冒泡排序的时间复杂函数式是：F(N)=(N-1)+(N-2)+…1=N*(N-1)/2//因此时间复杂度是O(N^2)
}

int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n;while (begin < end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid;elsereturn mid;}return -1;//二分查找的时间复杂度就比较“复杂”了//直接计算最坏，一次没找到就除以2，因此有多少个2就查找多少次，假设查找了x次，直到查早到最后一个元素（最坏情况），故有公式n/(2^x)=1，因此得到查早了x=ln(n)次//所以二分查找的时间复杂度是O(ln(N))
}

long long Factorial(size_t N)
{return N < 2 ? N : Factorial(N - 1) * N;//调用函数调用了N-1次，故时间复杂度为O(N)
}

注意：不是一层循环就O(n)两层就O(n^2)，要看程序的内在意义

⑥常见的时间复杂度对比O(1) < O(logN) < O(N) < O(N^2)

（3）空间复杂度的计算

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}

①代码解析：实际的们计算空间复杂度的时候，也不用计算如此精确的空间，只需要知道大概即可，于是这里我们也同样使用大O渐进表示法，空间复杂度不算空间，算变量个数。注意函数在运行所需要的栈空间（存储参数、局部变量、一些寄存器变量）在编译期间就确定好了，因此空间复杂度主要通过函数在运行的时候显式申请的额外空间来确定

②大O表示法：是用于描述函数渐进行为的数学符号

③推导方法：

• 用常数1取代运行时间中的所有加法常数
• 在修改后的运行函数中，只保留最高阶项
• 如果高阶项存在且不是1，则去除于这个项目相乘的常数

④推导例子：

void BubbleSort_1(int* a, int n)
{assert(a);for (size_t end = n; end > 0; --end){int exchange = 0;for (size_t i = 1; i < end; ++i){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}}if (exchange == 0)break;}//冒泡排序的空间复杂度是O(1)
}

long long* Fibonacci(size_t n)
{if (n == 0)return NULL;long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n; ++i){fibArray[i] = fibArray[i - 1] + fibArray[i - 2];}return fibArray;//空间复杂度是O(n)
}

long long Factorial_1(size_t N)
{return N < 2 ? N : Factorial(N - 1) * N;//空间复杂度是O(n)
}

long long Fib(size_t n)//斐波那契数列
{if (n < 3){return 1;}return Fib(n - 1) + Fib(n - 2);//时间复杂度可以认为是O(2^n):n^0+n^1+n^2+n^3+…2^(n-2)，注意这是按照全满的形式计算得到的，如果真的还要计算准确还需要再减少一部分//空间复杂度是O(n)而不是O(2^n)，这是由于函数栈帧的原因，空间被复用了（因为空间可以被重复使用，但是时间不可以）
}

2、有关的练习题目

（1） 面试题 17.04. 消失的数字 - 力扣（LeetCode）

感兴趣的话可以看看我的题解

（2） 189. 轮转数组 - 力扣（LeetCode）

感兴趣的话可以看看我的题解