Какова будет временная сложность следующей программы? - PullRequest
Новая
       26

Какова будет временная сложность следующей программы?

0 голосов
/ 13 февраля 2020

Может ли кто-нибудь найти временную сложность следующей python 3.6 программы:

Я попытался найти , и мой ответ равен O (N * n) , где N - диапазон самых первых l oop, а n - диапазон секунд для l oop это внутри первого для l oop

Эта программа для https://www.codechef.com/FEB20B/problems/SNUG_FIT проблемы с codechef . 

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)

Ответы [ 2 ]

1 голос
/ 13 февраля 2020

Значение для l oop равно O(N), и внутри него вы сортируете O(nlog(n)), поэтому в целом оно становится O(Nnlog(n)).

После этого у вас есть другое значение для l oop, которое выполняется O(n) .

Теперь общая сложность времени выглядит следующим образом:

O(N( nlogn + n)), что фактически составляет O(Nnlog(n))

0 голосов
/ 13 февраля 2020

@ Притам Банерджи написал -

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 вам очень поможет.

Спасибо.

...