while 循环执行 sum（n-1）时间的大 O-解网

问：

如果有人可以帮助我：

1- 这段代码的时间复杂度（Big O）是多少？

2- 如果这段代码的大 O = O（n^2），那么哪个更好使用（虽然像这段代码一样）或（两个嵌套的 for 循环）？

代码：

l = [1, 2, 3, 4, 6, 5]  // big O => O(1)
ll = list(l)  // big O => O(1)

a = 0  // big O => O(1)
b = 1  // big O => O(1)
x = 0  // big O => O(1)
y = 0  // big O => O(1)
 

while a < len(l)-1:  // big O  => O(?)
    
    x = l[a]  // big O => O(1)
    y = l[b]  // big O => O(1)

    if x > y :  // big O => O(1)

        ll[a] = 0   // big O => O(1)
        a += 1   // big O => O(1)
        b =a+1   // big O => O(1)
        
    elif b >= len(l)-1:   //big O => O(1)

        a += 1  // big O => O(1)
        b = a + 1  // big O => O(1)
        continue  // big O => O(?)
    
    else :  // big O => O(1)
        b += 1  // big O => O(1)
        continue   // big O => O(?)
        
print(ll) // big O => O(1)

在上述代码的最坏情况下，make while 循环执行了 （n-1） 时间的总和，例如：

if n = 1 then while loop will execute 0 time
if n = 2 then while loop will execute 1 time
if n = 3 then while loop will execute 3 time
if n = 4 then while loop will execute 6 time
if n = 6 then while loop will execute 15 time
.
.
.
if n = k then while loop will execute sum(k-1) time

我希望我的问题很清楚。

算法 while-loop big-o

“if n = 6 then while 循环将执行 15 次”：您提供的代码没有按照您所说的去做。当 n 为 6 时，循环进行 10 次迭代。这使您的问题模棱两可。你现在在问什么？使代码与描述保持一致？要使描述与代码保持一致？分析所描述算法的复杂性？要分析所提供代码的复杂性？

0赞 M.A 11/14/2023

@trincot，对不起，我试图找到与实际代码相似的想法。但实际上这是错误的例子。实际代码是传递 list[a1， a2， a3， a4...，an] 并将每个元素（a）与列表中的其余元素进行比较，如果 a<则用特殊值替换列表中的 a。因此，例如，如果输入列表 =[ 2， 1， 4， 3] 并且如果 a<an 则将 a 替换为（0）则 2<4 => 0 ， 1<4 => 0， 4> 3 所以 Not（ a<an）那么它将是相同的 a =>4， 3 列表中没有更多项目可以比较，所以它也将是相同的 =>3 然后输出列表 =[ 0 ， 0 , 4, 3 ].我希望我的问题很清楚。

0赞 trincot 11/14/2023

请更新您的问题。还要确保你问的问题很清楚：某段代码的时间复杂度，或者你必须解决代码挑战的问题，或者还是其他问题。

答：

1赞 trincot 11/16/2023 #1

代码的时间复杂度为 O（n²）。

关于您的分析的一些评论：

ll = list(l)  // big O => O(1)

该函数（在 Python 中）创建一个新列表，因此这实际上是 O（n）list

continue   // big O => O(?)

该语句需要恒定的时间才能执行，因此 O（1）。但是，在使用的地方，您可以简单地删除这些语句，因为它们不起作用（它们已经是在循环的当前迭代中执行的最后一个语句）。continuecontinue

print(ll) // big O => O(1)

打印列表所需的时间与列表的长度一样长（需要输出每个字符），因此这是 O（n）。另一方面，打印不应该成为复杂性分析的一部分。你最好把你的算法写成一个函数，它只返回结果。由调用者决定是否应该打印该列表，无论如何，这不是算法的一部分，也不应该进行分析。

主要问题是循环进行迭代的次数。如果我们丢弃以开头的块，则并获取可以从 {0,..,n−1} 获取的所有可能对的值，其中 .例如，如果 n 为 4，则和的值演变如下：ifif x > yaba < bab

迭代	一个	b
1	0	1
2	0	2
3	0	3
4	1	2
5	1	3
6	2	3

因此，有 3 次迭代，其中 0,2 次迭代，其中 1 次，以及 1 次迭代，其中 2。这样总共有 1+2+3+...+n−1 次迭代，这是一个三角形数，可以表示为 n（n−1）/2，即 O（n²）。aaa

O（n²）是最坏情况的复杂度，因为块可能导致增加的速度比上面解释的要快。在最好的情况下，你的输入将是一个递减序列（[5， 4， 3， 2， 1]），然后这个块将在外循环的每次迭代中执行，所以你只得到外循环的n-1次迭代，这使得它成为O（n）。if x > yaif

代码改进

在 Python 中，最好不要在循环变量上使用显式语句，而是使用迭代器或范围进行循环。例如，以下代码实现了相同的逻辑：a += 1

def solve(l):
    return [
        0 if any(l[b] < x for b in range(a + 1, len(l))) else x        
        for a, x in enumerate(l)
    ]

这里是用来找出是否有任何（之后）的。如果是这样，则应将值替换为 0，否则，我们保留原始值。此列表推导会创建一个新列表，因此它将调用与循环中的逻辑相结合。anybal[b] < l[a]axlist(l)

降低时间复杂度

我们还可以使用更有效的不同算法。如果我们向后遍历列表，那么我们可以跟踪到目前为止遇到的最小值。每当我们遇到大于该最小值的值时，我们都会将其替换为 0。这样我们就没有内部循环了，过程变成了 O（n）：

def solve(l):
    low = l[-1]  # keep track of the least value found so far
    result = [
        0 if (low := min(y, low)) < y else y
        for y in reversed(l)
    ]
    result.reverse()
    return result

好的，但是我必须用一些不同的情况编写算法工作，而不仅仅是用 0 或常量替换。不幸的是，其中一些情况需要用 y 或 x*y 替换。我的算法适用于所有这些情况，但如果可能的话，我需要像您的算法一样将时间复杂度降低到 O（n）。非常感谢您的帮助。

0赞 trincot 11/20/2023

同样的原则应该适用于其他替换值。如果您无法使其工作，您可以在尝试时发布一个新问题。

上一个：在 Java 中构造嵌套条件循环的循环覆盖率

下一个：如何在 bash 中一遍又一遍地运行命令直到成功？

while 循环执行 sum（n-1） 时间的大 O

the big O of while loop executed sum(n-1) time

评论

代码改进

降低时间复杂度

评论

while 循环执行 sum（n-1）时间的大 O