有大佬能解释下时间复杂度吗

两个 for 循环，内外循环都是 n 次，所以复杂度是 O(n^2)

我了解得也很粗浅，简单分享下我的理解吧。

假设输入样本数据量 x, 执行完所需耗时 y，他们可以构成一个二维函数图像。那么可以说：
时间复杂度是一种 “形状”

形状就分曲线和直线，O(N) 和 O(1) 的函数图像是直线。O(N^2), O(2^N),O(LogN) 是曲线。这五种基本的时间复杂度是各不相同的。

以上五种时间复杂度的乘积可直接表示为时间复杂度，它们之间的和以较高复杂度为最终复杂度。
例如：
O(N) * O(LogN) = O(N*LogN)

O(N) + O(LogN) = O(N)

样本数据大小为 N，按提的例子就是变量 len。时间复杂度的意义是按 N 这个的数据量，评估计算机需要完成多少次简单计算。简单计算指基本的赋值，运算等操作，对应的网络、IO等耗时操作要在算完时间复杂度后把这些额外因素加起来考虑。

常规的两级循环意味着需要 N*N 次逻辑计算, 也就是 O(n^2)，但你提供的例子里第二级循环会随着第一级循环的执行逐渐收缩，因此第一级循环 N 乘以第二级循环 1/2 N 时间复杂度为 1/2 * N^2, 前面的系数会省略掉记为 O(N^2)

常见问题：

1. 假如代码的循环或函数里有 3 行计算以及赋值的操作，为什么时间复杂度是 N^2 而不是 3 * N^2 呢？
   计算机的运算速度很快，因此习惯省略常数倍的系数。好比 5 秒钟能处理完的数据，现在翻倍了需要 10s。这属于同一性能指标，但如果用递归去实现诸如斐波那契数列 O(2^n) 这样的复杂度，样本数据在 40 - 50 之间每加一都会造成严重的耗时。可以理解为：时间复杂度忽略线性的计算增长，只关注跨数量级的性能影响。

2. 快排的时间复杂度是 N * logN, 为什么 log 没有底数？
   典型的二分查找可以比较准确地表示为 log2N，但这个底数在某些复杂的程序段里很难确认，而对数函数的图像又是大致相同的，在数据量很大的情况下，其底数的影响很小可以不用考虑。

最坏的情况下，第一次交换需要遍历n-1次，第二次遍历n-2次，总共需要(n-1)+(n-2)+..+1,根据等差数列求和公式，结果=n(n-1)/2=0.5n^2+0.5*n，然后去掉常数项系数和低次项，时间复杂度就是O(n^2)

简单理解其实可以理解为计算次数，比如一个函数，我传递1-∞，他都是计算明确的次数，1次，3次，8次，只要是可控的都记作O(1)， 如果计算次数最坏等于我输入的N，那就是O(n), 比如计算1-100的和，我输入100，最基础就计算100次，O(n)高斯算法优化时间复杂度，优化后为O(n/2)以此类推

那么问题来了，优化后的写法应该是什么样的呢 :smile:

(O)n ^2 推荐课程 王争老师的数据结构与算法之美

常数项化0+最差情况，O记。