我很难理解如何计算最坏情况下运行时间和运行时间。由于有一个段循环，运行时间是否必须为n 1，因为while循环必须运行1个额外的时间检查是否仍然有效？计算这些运行时间，但我似乎找不到任何好东西。与此类事物的链接将不胜感激。
def reverse1(lst):
rev_lst = []
i = 0
while(i < len(lst)):
rev_lst.insert(0, lst[i])
i += 1
return rev_lst
def reverse2(lst):
rev_lst = []
i = len(lst) - 1
while (i >= 0):
rev_lst.append(lst[i])
i -= 1
return rev_lst
常数因子或添加值对大O运行时间无关紧要，因此您对此进行了过度调整。运行时间是O(n)的CC_1（线性），而reverse1的O(n**2)（二次）（因为list.insert(0, x)本身是O(n)操作，执行O(n)次）。
Big-O运行时计算是关于算法随着输入尺寸增加而对无穷大的行为的行为，此处较小的因素也不重要。O(n + 1)与O(n)相同（与O(5n)相同；随着n的增加，5的恒定乘数与运行时的 Change 无关），O(n**2 + n)仍然只是O(n**2)等。>
由于迭代的数量是针对这两个功能的任何给定大小的给定大小固定的，因此"最差的"时间复杂性将与"最佳"one_answers"平均"相同。
在 reverse1中，将项目插入索引0的操作是index 0 cappem o（n），因为它必须将所有项目复制到其以下位置，并与while循环相结合。迭代输入列表的大小的次数，reverse1的时间复杂度为 o（n^2）。。
但是，reverse2中没有这样的问题，因为append方法仅需 o（1）执行，因此其总体时间复杂性是 o（n） o（n） o（n）。
我将为您提供数学上的解释，说明为什么额外的迭代和操作持续时间无关紧要。
这是o（n），因为big-oH的定义是对于f（n）∈O（g（n）），存在某些常数 k，使得f（n）＆lt;kg（n）。
考虑一种以F（n）= 10000N 15000000表示运行时的算法。您可以简化这种方法是考虑N：F（N）= N（10000 15000000/N）。对于最坏的情况，您只关心算法的性能，以实现n的超大值。因为在这种简化中，您将n除以n，所以在第二部分中，随着n的真正大，n的系数将接近10000，因为15000000/n接近n，如果n是巨大的，则接近0。因此，对于n> n（这意味着足够大的n值）必须存在一个常数k，以使f（n）＆lt;kn，例如k =10001。因此，f（n）∈O（n），它具有线性运行时效率。
话虽如此，这意味着即使您循环n 1次，您也不需要担心运行时不断差异。（对于多项式时间）唯一重要的部分是代码中N的最高程度。您的反向算法是O（n）运行时，即使您迭代n 1000次，它仍然是O（n）运行时。