以下程序的时间复杂度是多少

Question

谁能算出下面python3.6程序的时间复杂度:

我试图找到，我的答案是O(N*n)，其中 N 是第一个循环的范围，n 是 second for loop 的范围这是 在第一个 for 循环中

此程序用于解决 codechef 上的 https://www.codechef.com/FEB20B/problems/SNUG_FIT 问题。

N=int(input())
for _ in range(N):
    S=0
    n=int(input())
    A=list(map(int, input().split()))[:n] #Assume amount of inputs to be strictly of n numbers
    B=list(map(int, input().split()))[:n]
    A.sort();A.reverse()
    B.sort();B.reverse()

    for i in range(0,len(A)): # Here range is n (same as len(A))
        if A[i]>=B[i]:
            S=S+B[i]
        else:
            S=S+A[i]
    print(S)

Answer 1

for 循环是 O(N) 并且在其中排序 O(nlog(n)) 所以总体上它变成了 O(Nnlog(n)).

之后你有另一个运行 O(n).

的 for 循环

现在整体时间复杂度是这样的：

O(N( nlogn + n)) 实际上是 O(Nnlog(n))

Answer 2

@Pritam Banerjee 写道 -

O(N( nlogn + n)) which effectively is O(Nlog(n))

其实不然.

我连同代码描述得更清楚了。

N=int(input())
for _ in range(N):    # O(N)
    S=0
    n=int(input())
    # The following line is O(n)
    A=list(map(int, input().split()))[:n] #Assume amount of inputs to be strictly of n numbers
    # This line is also O(n)
    B=list(map(int, input().split()))[:n]
    A.sort();A.reverse()    # this is O(nlog(n))
    B.sort();B.reverse()    # this is also O(nlog(n))

    for i in range(0,len(A)): # Here range is n (same as len(A))  # this is O(n)
        if A[i]>=B[i]:
            S=S+B[i]
        else:
            S=S+A[i]
    print(S)

总的来说O(N( n + n + nlog(n) + nlog(n) + n)

我们可以这样计算 -

  O(N( n + n + nlog(n) + nlog(n) + n)
= O(N( 3n + 2nlog(n))
= O(N (n + nlog(n)) (we can eliminate const number when determining complexity)
= O(N(nlog(n)) (as n > nlog(n), so we can eliminate the small part)
= O(N*nlog(n))

所以总体复杂度是 O(N*nlog(n)，不是 O(Nlog(n)。

O(N*nlog(n) 和 O(Nlog(n) 的区别更大。

希望这篇post能对您有所帮助。

谢谢。

以下程序的时间复杂度是多少

What will be the time complexity of the following program

python

algorithm

complexity-theory

time-complexity

data-structures