Złożoność algorytmu

Jaka jest złożoność dla następującego problemu to O (n). Czy nie powinno to być O (n^2)? To dlatego, że zewnętrzna pętla to O (n), a wewnętrzna również O (n), zatem n * n = O (n^2)?Złożoność algorytmu

Arkusz odpowiedzi na to pytanie stwierdza, że odpowiedź brzmi: O (n). Jak to możliwe?

public static void q1d(int n) { 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
     count++; 
     for (int j = 0; j < n; j++) { 
      count++; 
     } 
    } 
}

Złożoność następującego problemu to O (n^2), w jaki sposób można to uzyskać? Czy ktoś może rozwinąć?

public static void q1E(int n) { 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
     count++; 
     for (int j = 0; j < n/2; j++) { 
      count++; 
     } 
    } 
}

Dzięki

Źródło

2012-01-17 Harminder

Myślę, że górny to O (n^2). Jakie są wątpliwości co do drugiego? – WordsWorth

Oznacza to, że odpowiedź udzielona przez mojego profesora jest niepoprawna hmm. – Harminder

wydaje się, że arkusz odpowiedzi zawiera błędy. – Zohaib

złożoność zarówno kod O (N * n)

Pierwsza

Zewnętrzna pętla jest n razy, a pętla wewnętrzna waha się od 0 to n-1 razy

czyli

total = 1 + 2 + 3 + 4 ... + n

które jeśli dodać arithmetic progression jest n * (n + 1)/2 jest O(n*n)

DRUGI

Zewnętrzna pętla jest n razy, a pętla wewnętrzna waha się od 0 to n-1/2 razy

tak

total = 1 + 1/2 + 3/2 + 4/2 ... + n/2

który jeśli dodać arytmetyczny jest n * (n + 1)/4 jest również O(n*n)

Źródło

2012-01-17 05:28:26

Więc jeśli n/2 nadal jest równe o (n)? Ale iteracja dla wewnętrznej pętli to połowa zewnętrznej pętli, która robi jakąkolwiek różnicę? – Harminder

@ user1085135: 'O (n)' ma znaczenie "liniowy". Nie ma znaczenia, jaka stała pomnożona przez, co ma znaczenie tylko, że jest ** liniowy – zerkms

Pierwszym przykładem jest O(n^2), więc wydaje się, że zrobiłem błąd. Aby obliczyć (nieformalnie) drugi przykład, możemy wykonać n * (n/2) = (n^2)/2 = O(n^2). Jeśli to nie ma sensu, musisz pójść i odświeżyć, co oznacza, że jest to O(n^k).

Źródło

2012-01-17 05:29:13 Yuushi

Pierwszy przypadek jest zdecydowanie O(n^2)

Drugi O(n^2) a także dlatego, że pominięcie stałe podczas obliczania Big O

Źródło

2012-01-17 05:31:20 zerkms

arkusza odpowiedź jest błędna, pierwszy algorytm jest wyraźnie O (n^2).

Zapis Big-Oh jest "najgorszym przypadkiem", więc przy obliczaniu wartości Big-Oh, zwykle ignorujemy multiplikacje/podziały według stałych.

W ten sposób, twój drugi przykład jest również O (n^2) w najgorszym przypadku, ponieważ, chociaż wewnętrzna pętla jest "tylko" 1/2 n, n jest jasnym czynnikiem ograniczającym. W praktyce drugi algorytm będzie mniejszy od operacji O (n^2) - ale Big-Oh ma być "najgorszym przypadkiem" (tj. Maksymalnym ograniczeniem) pomiaru, więc dokładna liczba operacji jest ignorowana na korzyść skupienie się na tym, jak zachowuje się algorytm, gdy n zbliża się do nieskończoności.

Źródło

2012-01-17 05:33:03 debracey

Drugi algorytm nie będzie mniejszy niż O (n^2), to jest * dokładnie * O (n^2). Podejrzewam, że nie do końca wiadomo, co właściwie oznacza "O (n^2)". Oznacza to, że gdy 'n' zbliża się do nieskończoności, czas działania wzrasta, ponieważ algorytm dla dwóch wartości' n' jest proporcjonalny do różnicy pomiędzy tymi wartościami "n" do kwadratu. –

Nie. W praktyce rzeczywista złożoność czasu algorytmu będzie nieco mniejsza niż O (n^2). Jednakże, ponieważ Big-Oh jest maksymalnym ograniczeniem, mówimy, że jest to O (n^2). Masz rację, że współczynnik "n/2" jest wyraźnie ograniczony przez n - jak wskazałem w mojej odpowiedzi. Istnieją inne pomiary ograniczające (np. Big-Theta), które inaczej obliczają współczynnik graniczny. – debracey

Jak myślisz, dlaczego rzeczywisty czas złożoności algorytmu będzie mniejszy niż O (n^2)? Twierdzę, że będzie to dokładnie * O (n^2), ponieważ złożoność algorytmu * właśnie * pasuje do * definicji * O (n^2). Jeśli to nie * dokładnie * O (n^2), to nic nie jest. My * mówimy * że jest O (n^2), ponieważ to ** jest ** O (n^2). Wydaje się, że chcecie, by było to niewyraźne, mylące i nieprecyzyjne, gdy jest absolutnie, krystalicznie czyste. –

Oba są O(n^2). Twoja odpowiedź jest błędna. Lub możesz napisać pytanie niepoprawnie.

Źródło

2012-07-17 06:53:55 Shashwat

Złożoność algorytmu

Odpowiedz

Powiązane problemy