计算函数的时间复杂度
我在考虑如何正确计算这个函数的时间复杂度:
def foo(lst):
jump = 1
total = 0
while jump < len(lst):
for i in range(0, len(lst), jump):
total += i
jump = jump * 2
return total
我假设它是 O（n），其中 n 是列表的长度。我们的 while 循环是 O（n），for 循环也是 O（n），
这意味着我们得到了 2*O（n），等于 O（n）。
我说的对吗？
共有1个答案
您的计算有错误，对于嵌套循环，我们将外部循环的复杂度乘以内循环的复杂度以获得完整的复杂度。
如果 n 是列表的长度，那么 while 循环运行 log（n） 时间，就像每次我们使用 jump = jump * 2 一样
当＜code＞jump＝1＜/code＞时，内循环是这样的，＜code＞n/1＜/code>次，当jump＝2时，＜code＜n/2＜/code＞次，所以内循环的复杂性是这样的：（n/1）（n/2）（n/4）（n/8）……直到logn次
因此，总时间复杂度= n(1 1/2 1/4 1/8 …直到logn)。这里< code>n的系数可以忽略不计，所以复杂度为< code>O(n)
-
如何计算以下函数的时间复杂度？ 现在，我知道循环具有O（n）时间复杂度，但在这种情况下，I以更快的速度增长。一次又一次地迭代，我发现，对于每一个第m次迭代，I=m^2。但我仍然不知道如何计算大O。
-
这里是一个递归函数。它遍历字符串映射()。检查()如果等于所需的字符串()，则打印它()，并再次为该执行函数。 停下来没有规则，似乎完全是随机的。这个函数的时间复杂度是如何计算出来的？
-
我想用尽可能多的方法解决塔式料斗问题，并计算每种方法的时间复杂性（仅用于自我练习）。解决方案之一是： 我知道递归时间复杂度计算的一般想法，但我在分析注释行（在 for 循环内）时遇到了麻烦。通常我用 ）计算时间复杂度，并用一般表达式（例如 T（n-k））降低它，直到我达到基本情况并且可以用 n 表示 k，但是 for 循环的时间复杂度是多少？
-
我已经通过谷歌和堆栈溢出搜索，但我没有找到一个关于如何计算时间复杂度的清晰而直接的解释。 说代码像下面这样简单： 说一个像下面这样的循环： 这将只执行一次。 时间实际上被计算为而不是声明。
-
我正在尝试分析一个算法的时间复杂度。 下面的算法旨在只检查数组的一部分，所以如果它没有多大意义，请不要担心。 我对计算循环周围的时间复杂度很困惑，请看看我的评论。 这是否意味着我们有: T（N） = （C2 C4 C5）N （C1 C3 C6） T(N) = C7*N (C8) T（N）=N？？ 循环中的所有内容都是*N？ 先谢谢！
-
我写了一个函数来寻找目标值在给定数组中应该插入的位置。我们假设数组有不同的值，并按升序排序。我的解必须是O(log N)时间复杂度 此代码的复杂性是否为O（log N）？