算法(Algorithm)
什么是算法?
在数据结构中，算法是解决问题或执行任务的一系列有序步骤。
它是一种有限的、确定性的、可执行的指令集，用于完成特定的任务，
例如数据的排序、搜索或管理。
算法特点
1. 有穷性：算法必须在执行有限步骤后结束。
2. 确定性：算法的每一步骤都必须有明确的定义，不会导致歧义。
3. 输入： 算法有0个或多个输入，这些输入是算法执行所需的初始数据。
4. 输出： 算法至少有一个输出，表示算法执行的结果。
5. 可行性： 算法的每一步都必须能够通过执行有限次数的基本操作来实现。
算法效率
算法的效率通常通过时间复杂度和空间复杂度来衡量，
时间复杂度表示算法执行所需时间与输入规模的关系，
空间复杂度表示算法执行所需的存储空间量。
选择或设计算法时，通常会考虑这些因素以优化性能。
这篇文章要解决的问题
导图
时间复杂度
是什么?
在数据结构中，时间复杂度是衡量算法执行所需时间的一个指标。
它描述了算法执行时间随输入数据规模增长的变化趋势，
通常用大O符号（Big O Notation）来表示。
如何使用大O表示法：
- 确定算法的执行步骤：分析算法中的循环、递归等结构，确定算法的执行步骤。
- 评估执行次数与输入规模的关系：确定算法中每一步或每一组步骤执行的次数与输入规模n的关系。
- 简化表达式：在大O表示法中，我们通常只保留最高次项，并去掉常数因子和低阶项，因为它们对算法的渐进行为影响较小。
- 确定上界：大O表示法关注的是算法性能的上界，即在最坏情况下的性能。
示例
假设有一个算法，其执行步骤可以表示为：
第一步执行10次 （常数时间操作）
第二步执行n次 （线性操作）
第三步执行n^2次（平方操作）
使用大O表示法，我们可以忽略第一步（因为它是常数时间操作），并简化为：
总时间复杂度：O(n^2)
这意味着算法的时间复杂度是平方级别的，与输入规模的平方成正比。
举例
样例①
// 请计算一下Func1基本操作执行了多少次？ 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); }
样例②
//计算Func2的时间复杂度： 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); }
样例③
//计算Func3的时间复杂度： 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); }
样例④
//计算Func4的时间复杂度： void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++k) { ++count; } printf("%d\n", count + N); }
样例⑤
//计算strchr的时间复杂度： const char* strchr(const char* str, int character); //strchr库函数：在str字符数组中查找一个字符
这个的时间复杂度应分三种情况
①最好情况: 第一次就找了
②平均情况: 找的字符在整个的中间
③ 最坏情况: 最后一次才找到
样例⑥
//计算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; } } }
说明:冒泡的最坏情况:
1.完全逆序的数组 2.每次循环只能排定一个元素
样例⑦
//计算BinarySearch的时间复杂度： int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n - 1; // [begin, end]：begin和end是左闭右闭区间，因此有=号 while (begin <= end) { int mid = begin + ((end - begin) >> 1); if (a[mid] < x) { begin = mid + 1; } else if (a[mid] > x) { end = mid - 1; } else { return mid; } } return -1; }
二分查找的本质是:原有N个数,找一次范围缩小一半
最好的情况:
缩小第一次就找到了,(也就是这个数在中间值)
时间复杂度为O(1)
最坏的情况:
缩小多少次范围的一半,就找了多少次
设找了x次,所以 2^x = N
x = logN ,最坏的情况时间复杂度为O(logN)
样例⑧
//计算阶乘递归Fac的时间复杂度： long long Fac(size_t N) { if (0 == N) { return 1; } return Fac(N-1)*N; }
由于递归调用的次数与输入 N 成正比，并且每次调用中的工作量是常数时间的（乘法操作），
所以总的时间复杂度是线性的，即 O(N)。
样例⑨
//计算斐波那契递归Fib的时间复杂度： long long Fib(size_t N) { if (N < 3) { return 1; } return Fib(N - 1) + Fib(N - 2); }
该递归函数的时间复杂度是指数级的，具体来说是 O(2^N)，原因如下：
1.递归树：每次调用 Fib(N) 都会生成两个新的递归调用 Fib(N - 1) 和 Fib(N - 2)。这形成了一2.个递归树，其中每个节点都会生成两个子节点，直到达到递归基（N < 3）。
递归调用次数：在递归树中，每个节点都会进行两次递归调用，除了最底层的节点（即递归基）。这意味着递归调用的总数大约是 2 的 N 次幂减去一些小的常数项（因为最底层的一些节点只需要一次调用）。
3.重叠子问题：在递归树中，许多子问题是重叠的，即同一个斐波那契数会被多次计算。
例如，Fib(4) 会被计算两次，一次在计算 Fib(5) 时，另一次在计算 Fib(6) 时。这导致了很多不必要的计算。
小结:由于每个递归调用都会生成两个新的递归调用，递归调用的总数大约是 2^N，因此时间复杂度是 O(2^N)。
总结
1.递归算法(时间复杂度):每次递归子函数消耗加起来
2.分析时间复杂度时,为了确保分析正确,需要对该 代码/函数 具体分析它的最好情况,最坏情况和平均情况等(不能简单地看for,while循环)
空间复杂度
是什么?
空间复杂度是一个用于描述算法在执行过程中所使用的额外空间（除了输入数据所占用的空间之外）的量度。
这里的“额外空间”通常指的是算法运行时的内存使用量。
所以空间复杂度计算的是变量的个数,也使用大O表示法
举例
样例①
//计算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; } } }
样例②
//计算Fibonacci的空间复杂度： //返回斐波那契数列的前n项 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; }
样例③
//计算阶乘递归Fac的空间复杂度： long long Fac(size_t N) { if (N == 0) { return 1; } return Fac(N-1)*N; }
空间复杂度和时间复杂度的区别
| 时间复杂度 | 空间复杂度 |
| 算法执行所需的时间 | 算法执行所需的额外空间 |
