这个解决方案的时间复杂度是多少？

Question

我了解基本的时间复杂度，但我很难知道时间复杂度何时与日志相关。这是我对 HackerRank 冰淇淋店问题的解决方案：https://www.hackerrank.com/challenges/icecream-parlor/problem

def icecreamParlor(m, arr):

    for i in range(len(arr)):
        for k in range(i+1, len(arr), 1):
        
            if arr[i] + arr[k] == m:
                return [i+1, k+1]

据我了解，嵌套循环通常是 O(n^2)；但是，由于我没有在第二个循环中每次都遍历整个列表，所以这种情况会改变吗？当我从内部循环的 i 开始时，循环它所花费的时间越来越少。这个的时间复杂度是多少？

Answer 1

它仍然是 O(n^2) - 它显然会比 2 个嵌套循环快，每个嵌套循环都有 n 次迭代，但你仍然有 2 个循环 variable-dependent。如果还有什么问题lmk :)

Answer 2

在顶层，您循环 N 次。对于这些循环中的每个 i，您将循环一些 M = N-i 次。请注意，这意味着 M 平均为 N 的一半：(5+4+3+2+1+0) == (5+5+5+5+5)/2。所以整体的时间复杂度是O(N * N/2)，相当于O(N*N)或者O(N**2).

Answer 3

我推荐使用 Big-O python 库！你只需要导入它，你就可以运行你的代码在里面 :) 这将在多个项目中帮助您。继续努力！

Answer 4

这仍然是 O(n^2)。你的外循环正在做 N 工作，而你的内循环正在做 n-1 工作。

如果您要写出每个循环的 i 和 k 计数，对于 len(arr) = 5，您会得到类似这样的结果

i = 1 k = 2,3,4,5
i = 2 k = 3,4,5
i = 3 k = 4,5
i = 4 k = 5
i = 5

这种 for 循环模式类似于三角数 (https://en.wikipedia.org/wiki/Triangular_number)。从这篇文章中，找到任何给定 N 的三角形数的方法是 N + 1 选择 2。这给了我们公式 N(N+1)/2。渐近这个函数给了我们 O(n^2) 行为

这个解决方案的时间复杂度是多少？

What is the time complexity of this solution?

python

performance

time-complexity

big-o