数据结构与算法（C++）– 算法分析

算法分析包括：时间复杂度和空间复杂度分析。以下主要是时间复杂度的分析。

1、数学定义

O 表示前面是后面的下界，后面是前面的上界Ω 表示前面是后面的上界，后面是前面的下界

2、运算法则

计算大O时，忽略低阶项和常数因子。

T(N) = O(N^2) = O(2N^2) = O(N^2+N)可以用求极限 lim f(N)/g(N) 来确定 f(N) 和 g(N) 的相对增长率，必要时可以使用洛必达法则。

极限 = 0： f(N) = o(g(N) )极限是常数但！= 0： f(N) = θ(g(N) )极限 = 正无穷： g(N) = o(f(N) )极限不存在：无关系

3、运行时间的计算

分析算法的时间复杂度时，不考虑内存访问时间。若无指定，所求的时间复杂度用最坏的情况表示有时也会用平均时间来衡量，但通常准确计算平均时间比较困难

时间计算的一般法则：

for 循环：O(N)嵌套 for 循环(n层)：O(N^n)顺序语句：各个语句的运行时间求和if/else 语句：判断时间 + 两者较长

时间复杂度排序：

4、最大子序列和

求一个序列中，连续元素和最大的子序列

int maxSubSum(const vector<int>& a){int maxSum = 0; thisSum = 0;for(int i = 0; j<a.size(); ++j){thisSum += a[j];if(thisSum > maxSum)maxSum = thisSum;else if(thisSum < 0)thisSum = 0;}return maxSum}

时间复杂度为 O(N)如果当前序列和大于当前的最大子序列和，更新最大子序列和如果序列和 < 0 表示这将不会对后面和做出任何贡献，舍弃

如果觉得《数据结构与算法（C++）-- 算法分析》对你有帮助，请点赞、收藏，并留下你的观点哦！