Czy złożoność czasowa tego algorytmu Θ (n)?

Chcę znaleźć złożoność czasową następującego algorytmuCzy złożoność czasowa tego algorytmu Θ (n)?

for i=1 to n do 
    j=i 
    while j<n do 
     j=2*j

zrobiłem moje obliczenia i stwierdziliśmy, że T(n) = log(n^n/n!).

Ale poprawna odpowiedź ma być T(n) = Θ(n).

Czy myliłem się? A może log(n^n/n!) = Θ(n)?

Źródło

2016-06-06 Da Mike

pierwsze wrażenie i że O (N^2) w pętli ist n i wewnętrzną, gdy jest również brak –

@SeekAddo Myślę, że jeśli wykonasz jakieś obliczenia, przekonasz się, że istnieje lepsza granica niż n^2 –

Wewnętrzna pętla ma czas działania 'O (log (ni)) ', więc moja pierwsza myśl byłaby" O (n * log (n)) 'gdybyś nie powiedział, że rozwiązaniem jest' O (n) ' – Keiwan

Chodzi o to, że twoja formuła jest odpowiednikiem ich. Trzeba tylko wiedzieć trochę matematyki:

Gdzie pierwsze 2 transformacje są tylko podstawowe właściwości dziennika, a trzeci jest Stirling's approximation.

I wyraźnie każdy wie, że n = Θ(n)

Źródło

2016-06-06 20:38:19

Plus za wzmiankę o przybliżeniu Stirlinga. – Shravan40

Wielkie dzięki, panie Dali! –

Nie sądzę, że Salvador Dali prezentowane prawidłowego dowodu, mimo że jest blisko. Błędem jest przyjęcie, że jako stała obok pierwszego f może być większe niż następne obok drugiego.

prawidłowa byłaby:

Gdzie

Źródło

2016-06-06 21:15:42 kkonrad

Ale wewnętrzna pętla jest wykonywana dokładnie "sufitu {log (n^n/n!)} - 1" razy. Brak notacji Big-O na tym –

Gdzie dokładnie widziałeś mnie odejmując 'O (f (n))' i 'O (g (n))'? Uprościłem tylko ekspresję OP i powiedziałem, że n to O (n). Więc po prostu przepisałeś moją odpowiedź trochę inaczej. –

W twoim przypadku pokazujesz, że n log n - n log n + n is = n, co nie jest prawdziwe w notacjach asymptotycznych i nie może być użyte do obliczenia złożoności algorytmu. Nie sądzę, żeby to było przepisywanie odpowiedzi, ponieważ nie sądzę, że Twoja jest poprawna. Zrobiłeś dobry argument na temat używania formuły Stirlinga ... – kkonrad

Złożoność jest Θ(n). Dokładny czas pracy jest 2n

to sprawdzić:

import math 

def get_complexity(n): 
    counter = 0 

    for i in range(1,n): 
     j = i 
     while j < n: 
      j = 2 * j 
      counter += 1 

    print('n: %16d\niterations: %6d\n2n: %14d \n' % (n, counter, 2*n)) 


for ten in range(1,5): 
    get_complexity(10 ** ten)

Wydajność:

n:    10 
counter:   16 
2n:    20 

n:    100 
counter:  194 
2n:    200 

n:    1000 
counter:  1990 
2n:   2000 

n:   10000 
counter:  19990 
2n:   20000 

n:   100000 
counter:  199988 
2n:   200000

Źródło

2016-06-07 12:18:34

Nie sądzę, że to zrobi dużą różnicę, ale myślę, że powinieneś zmienić 'dla i w zakresie (1, n)' na 'dla mnie w zakres (1, n + 1) '. Bo 'range (1, n)' daje '[1, 2, 3, .. n-1]' jeśli się nie mylę. –

Czy złożoność czasowa tego algorytmu Θ (n)?

Odpowiedz

Powiązane problemy