问：嵌套while循环的大O在for循环里面

Question

我实现了在 n 长列表中计算从 1 到 n 的整数的出现次数。条件是不允许有额外的数据结构。仅操作原始列表。打印出整数及其计数
例如：

org_arr  = [3, 4, 3, 1]
count_int(org_arr )
for i, item in enumerate(org_arr , 1):
    print(i, '->', abs(item))

输出：

1 -> 1
2 -> 0
3 -> 2
4 -> 1

下面是我对 count_int()

的实现

def count_int(arr):
    for i, check_index in enumerate(arr):
        if check_index > 0:
            arr[i] = 0
            while True:
                next_item = arr[check_index-1]
                if next_item < 0:
                    arr[check_index-1] -= 1
                    break
                elif next_item > 0:                     
                    arr[check_index-1] = -1
                    check_index = next_item
                else:
                    arr[check_index-1] = -1
                    break

count_int() 使用负计数和索引 = k - 1 表示整数 k（指定 1 <= k <= n）来实现目标。运行后，原数组org_arr为[-1, 0, -2, -1]

我的问题是关于这个函数的大O。是 O(n) 还是 O(n^2)？

在最坏的情况下，org_arr[0]的for循环需要n-1次while循环才能将org_arr[1]的值设置为org_arr[ n-1] 负计数器。之后，while 循环将永远不会被调用。因此，它是 (n-1) 个 while 循环 + (n-1) 个 for 循环。这将是 2(n-1)。所以，它是 O(n)，但我朋友说它是 O(n^2)，因为 for 循环中有一个嵌套的 while 循环。

Answer 1

您的分析是正确的。在许多情况下，嵌套循环会导致 O(n^2) 性能，但在这种情况下，同一索引不能在 while 循环中两次为正。这意味着 while 循环在所有迭代中的总运行时间最多是一个常数的 n 倍加上另一个常数的 n 倍，即 O(n)（因为它最多可以检查 n一个循环中的元素，但之后如果再次命中相同的元素，将在恒定时间内 return ）。当然它不能运行比 O(n) 快，因为 for 循环接触每个元素一次。

问：嵌套while循环的大O在for循环里面

Q: big O of nested while loop inside for loop

python

algorithm

big-o

nested-loops