W jaki sposób algorytm może mieć dwie najgorsze komplikacje?

Question

Steven Skiena jest Algorytmów podręcznika Rozdział 1 ćwiczenie ma na to pytanie:

Niech P będzie problemem. Najgorsza złożoność czasowa P to O (n^2). Najgorsza złożoność czasowa P to także Ω (n log n). Niech A będzie algorytmem , który rozwiąże P. Który podzbiór poniższych instrukcji jest zgodny z tą informacją o złożoności P?

• A ma najgorszy czas złożoności O (n^2).
• A ma najgorszy czas złożoności O (n^3/2).
• A ma najgorszy czas złożoności O (n).
• A ma najgorszy czas złożoności ⍬ (n^2).
• A ma najgorszy czas złożoności ⍬ (n^3).

W jaki sposób algorytm może mieć dwie najgorsze komplikacje czasowe? Czy autor próbuje powiedzieć, że dla pewnej wartości n (powiedzmy np. 300) górna granica dla algorytmu zapisanego do rozwiązania P jest rzędu O (n^2), podczas gdy dla innej wartości n (powiedzmy np. 3000) ten sam najgorszy przypadek algorytmu to Ω (n log n)?

Answer 1

Odpowiedź na Twoje pytanie

jest autor chce powiedzieć, że dla niektórych wartości n (powiedzmy na przykład 300) górna granica dla algorytmu pisemnego rozwiązywania P jest rzędu O (n^2) podczas gdy dla innej wartości n (powiedzmy np. 3000) ten sam algorytm najgorszego przypadku był Ω (n log n)?

to nr. Nie tak działają funkcje złożoności. :) Nie mówimy o różnych klasach złożoności dla różnych wartości n. Złożoność odnosi się do całego algorytmu, a nie do algorytmu w określonych rozmiarach. Algorytm ma funkcję złożoności pojedynczego czasu T (n), która oblicza, ile kroków jest wymaganych do przeprowadzenia obliczeń dla wielkości wejściowej n.

W problemu, podane są dwie informacje:

• W najgorszym przypadku złożoność wynosi O (n^2)

• W najgorszym przypadku złożoność jest Ω (n log n)

Wszystko to oznacza, że ​​możemy odebrać o stałych C1, C2, N1 i N2, takie, że dla naszego algorytmu w funkcji T (n), mamy

• T (n) ≤ C1 * n^2 dla każdego n ≥ N1

• T (n) ≥ c2 * n log n dla wszystkich n ≥ N2

W innych słowa, nasze T (n) jest "asymptotycznie ograniczone poniżej" przez pewien stały czas n log n i "asymptotycznie ograniczony powyżej" przez pewne stałe czasy n^2. Może to być dowolna "między" funkcją w stylu n log n i funkcją stylu n^2. Może to być nawet n log n (ponieważ jest on ograniczony przez n^2) lub może być n^2 (ponieważ jest ograniczony poniżej przez n log n. Może to być coś pośredniego, np. N (log n) (log n) .

To nie jest tak, że algorytm ma "wiele najgorszych przypadków" w tym sensie, że ma różne zachowania. . inna

teraz jest możliwe że masz jakąś funkcję "weird" tak:

def p(n): 
    if n is even: 
     print n log n stars 
    else: 
     print n*2 stars 

Ten algorytm robi szalone h ave granice określone w problemie z książki Skiena. I nie ma złożoności Θ. Być może o tym myślałeś, ale zauważ, że funkcja złożoności nie jest tak dziwna, abyśmy mogli powiedzieć, że górna i dolna granica różnią się. Należy pamiętać, że górna i dolna granica nie są określone, chyba że wyraźnie stwierdzono, że tak jest.