Definicja kolejności wzrostu od Reynolds & Tymann

47

Czytam książkę Principles of Computer Science (2008) Carla Reynoldsa i Paula Tymanna (wydaną przez Zarysy Schauma).

Drugi rozdział przedstawia algorytmy z przykładem wyszukiwania sekwencyjnego, które po prostu iteruje listę nazw i zwraca PRAWDA, jeśli dana nazwa zostanie znaleziona na liście.

Autor kontynuuje (strona 17):

Mówimy, że „kolejność wzrostu” algorytmu wyszukiwania sekwencyjnego to n. Zapis tego jest T (n). Mówimy również, że algorytm, którego kolejność wzrostu mieści się w pewnym stałym współczynniku T (n), ma wartość theta NL. „Wyszukiwanie sekwencyjne ma theta n.” Rozmiar problemu wynosi n, długość przeszukiwanej listy.

Naprawdę trudno mi się na to zgodzić. Książka jest pełna błędów, więc nie jestem pewien, czy coś mi brakuje, czy literówka w powyższym akapicie. Ogólnie angielski rzadko kiedy zdanie kończy się na „... powiedz”.

Jestem zdezorientowany.

Co oznacza skrót T? Książka nie wyjaśnia. Czy to czas, czy Theta?

Jeśli „theta NL” oznacza „Wyszukiwanie sekwencyjne ma theta n”. Co oznacza L? „Liniowy” czy „długość”?

Napisałem do wydawców z prośbą o wyjaśnienie. Powiedzieli, że przekażą moją wiadomość autorom. Nie odpowiedzieli. Próbowałem też spojrzeć na inne źródła, ale wciąż mam dokuczliwe wrażenie, że coś źle rozumiem - więc nie mogę odpocząć, dopóki nie zdekoduję tego akapitu.

Jeśli ktoś ma kopię tej książki i zrozumiał ten akapit. Byłbym wdzięczny za informację, czy ten akapit jest dokładny, czy wyjaśnienie go innymi słowy. Dzięki.

— JW.
źródło

Złożoność czasowa T (n), z Wikipedii : „Ponieważ czas działania algorytmu może być różny dla różnych danych wejściowych o tym samym rozmiarze, powszechnie stosuje się złożoność czasową algorytmu najgorszego przypadku, oznaczoną jako T (n), która jest zdefiniowana jako maksymalny czas potrzebny na dane wejściowe o rozmiarze n. Mniej powszechny i zwykle wyraźnie określony, jest miarą złożoności średnich przypadków. Złożoności czasowe są klasyfikowane według charakteru funkcji T (n). Na przykład algorytm z T (n) = O (n) nazywa się algorytmem liniowym czasu, a [...] "

— Stefan

1

Sądzę, że to ta książka, a oprócz niegwiezdnej recenzji, którą właśnie opuściłem, dziś jest jeszcze inna data, która prawdopodobnie nie jest przypadkiem!

— Jason C

Takie użycie powiedzenia wydaje się być definicją rzadziej używaną: zakładać lub zakładać. Pomyśl o tym jako o „... powiedzmy”. Nadal nie jestem pewien, czy to zdanie ma sens.

— Roger Krueger

77

Akapit jest błędny. Niestety wygląda to dokładnie na coś, co student, który nie rozumie materiału, napisałby jako odpowiedź na ćwiczenie. W tego rodzaju bzdurach nie ma miejsca w podręczniku. Nie rób gwałtownych ruchów. Odłóż książkę. Odsuń się od książki.

$T(n)$

$T(n)$ $T$ $n$

\begin{aligned} T (1) & = k \\ T (n) & = T (n - 1) + \log n for n > 1 \end{aligned}

$\begin{align*} T(1)&=k\\ T(n)&=T(n-1)+\log n \quad\text{for }n>1 \end{align*}$

T

$T$

T (n) = blah

$T(n)=\text{blah}$

T

$T$

T

$T$

$T(n)$ $n$

To oczywiście zostało zniekształcone. Myślę, że autorzy zamierzali napisać coś takiego,

$T(n)$ $\boldsymbol{n}$ $n$

Ale proszę, nie mówimy, że „ma theta ”, tak jak, jeśli jest twoją notacją wysokości, nie powiedziałbyś „John ma 180 cm”. To po prostu nieprawidłowa forma słów. Mówimy właściwie: „Czas działania algorytmu to theta (lub theta )”. Zwróć uwagę w szczególności, że to narzędzie do mówienia o funkcjach matematycznych, a nie algorytmach. Theta nie oznacza, że czas działania jest czymś; raczej jest to coś, czego możesz użyć do rozmowy o czasie działania. $n$ $h$ $h$ $n$ $n$ $\Theta$

Nawiasem mówiąc , „NL” oznacza niedeterministyczny obszar logiczny klasy złożoności , co nie ma żadnego sensu w pozycji, w jakiej pojawił się w pierwotnym cytacie.

— David Richerby
źródło

12

Pierwszy akapit sprawił, że się uśmiechnąłem, ponieważ jest to dokładnie to, co powiedziałaby policja informatyki :-) (+1 też, to dobra odpowiedź).

— Juho,

3

Dziękuję bardzo za wyjaśnienie. Jest to naprawdę bardzo pomocne i teraz czuję, że rozumiem to trochę lepiej (a przynajmniej nie czuję niepokoju w moim mózgu, że nie rozumiem tego akapitu). Mogę się teraz zrelaksować.

— JW.

2

Wygląda na to, że autor próbuje wyjaśnić notację Big O , ale zmienił jej nazwę na bez żadnego konkretnego powodu i całkowicie zniekształcił tekst. $T$

Aby dobrze opisać notację Big O (a także little-o i Theta), polecam książkę MIT „ Wprowadzenie do algorytmów” autorstwa prof. Leisersona.

Wydaje się, że jednym ważnym rozróżnieniem jest to, że odnosi się do całkowitej złożoności algorytmu, którą jest zazwyczaj czas , przestrzeń lub jedno i drugie. (np. niektóre algorytmy działają wolniej z większymi zestawami danych; niektóre wymagają więcej miejsca do przechowywania większych danych; a niektóre wymagają więcej czasu i więcej miejsca) . $O-notation$

Wydaje się, że ta odnosi się tylko do pomiaru czasu algorytmu i nie uwzględnia wymagań dotyczących pamięci. $T-notation$

— Abelenky
źródło

1

Nie brzmi to tak, jakby w ogóle próbowali wyjaśnić duże O - mówią wprost o theta.

— David Richerby,

Tekst prof. Leisersona szczegółowo opisuje Theta jako bardziej precyzyjną odmianę BigO. Zdaję sobie sprawę, że mogą istnieć inne definicje Theta, ale znana mi jest theta związana z BigO.

— abelenky

2

Nie sądzę, że o to chodzi. Zamiast tego podejrzewam, że jest to powszechna niechęć do pisania „T (n) = n” i zakładania (bez wyraźnego stwierdzenia), że wszyscy wywnioskują, że T (n) odnosi się do czasu działania, a konkretnie czasu działania algorytmu, który oni mieć na uwadze, a n oznacza rozmiar danych wejściowych.

— DW