2023年6月29日发(作者：)

算法时间复杂度渐进阶排序_Python算法中的时间复杂度在实现算法的时候，通常会从两⽅⾯考虑算法的复杂度，即时间复杂度和空间复杂度。顾名思义，时间复杂度⽤于度量算法的计算⼯作量，空间复杂度⽤于度量算法占⽤的内存空间。本⽂将从时间复杂度的概念出发，结合实际代码⽰例分析算法的时间复杂度。渐进时间复杂度时间复杂度是算法运算所消耗的时间，因为不同⼤⼩的输⼊数据，算法处理所要消耗的时间是不同的，因此评估⼀个算运⾏时间是⽐较困难的，所以通常关注的是时间频度，即算法运⾏计算操作的次数，记为T(n)，其中n称为问题的规模。同样，因为n是⼀个变量，n发⽣变化时，时间频度T(n) 也在发⽣变化，我们称时间复杂度的极限情形称为算法的渐近时间复杂度，记为O(n)，不包含函数的低阶和⾸项系数。我们以如下 例⼦来解释⼀下：如上例⼦中，我们根据代码上执⾏的平均时间假设，计算 run_time(n) 函数的时间复杂度，如下：上述时间复杂度计算公式T(n) ，是我们对函数 run_time(n) 进⾏的时间复杂度的估算。当n 值⾮常⼤的时候，T(n)函数中常数项 time0 以及n的系数 (time1+time2+time3+time4) 对n的影响也可以忽略不计了，因此这⾥函数run_time(n) 的时间复杂度我们可以表⽰为O(n)。因为我们计算的是极限状态下(如，n⾮常⼤)的时间复杂度，因此其中存在以下两种特性：低阶项相对于⾼阶项产⽣的影响很⼩，可以忽略不计。最⾼项系数对最⾼项的影响也很⼩，可以忽略不计。根据上述两种特性，时间复杂度的计算⽅法：1.只取最⾼阶项，去掉低阶项。2.去掉最⾼项的系数。3.针对常数阶，取时间复杂度为O(1)。我们通过下⾯例⼦理解⼀下常见的时间复杂度，如下：时间复杂度：常数阶 O(1)时间复杂度：线性阶 O(n)时间复杂度：线性阶 O(n)时间复杂度：平⽅阶 O(n^2)时间复杂度：平⽅阶 O(n^2)时间复杂度：平⽅阶 O(n^2)时间复杂度：⽴⽅阶 O(n^3)时间复杂度：对数阶 O(logn)随着问题规模n的不断增⼤，上述时间复杂度不断增⼤，算法的执⾏效率越低，时间复杂度排序如下：练习⼀下如下count_sort 函数实现了计数排序，列表中的数范围都在0到100之间，列表长度⼤约为100万。如上count_sort 函数的 空间复杂度为 O(n)，公式如下：