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

Question

谁能找到以下python 3.6程序的时间复杂度：

我试图找到并且我的答案是O（N * n），其中N是第一个循环的范围，而n是second for loop的范围是in the first for loop

此程序用于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(Nlog(n))

Answer 2

@@ Pritam Banerjee写道-

O(N( nlogn + n))，实际上是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对您有很大帮助。

谢谢。