Często niektóre odpowiedzi wspominają, że dane rozwiązanie to liniowe, lub że inne to kwadratowe.Czas liniowy v.s. Kwadratowy czas
Jak sprawić różnicę/określić, co jest czym?
Czy ktoś może wyjaśnić to, najprostszy możliwy sposób, dla tych, którzy mnie jeszcze nie znają?
Metoda jest liniowa, gdy czas jej trwania wzrasta liniowo wraz z liczbą zaangażowanych elementów.Na przykład, do pętli, która drukuje elementy tablicy jest w przybliżeniu liniowa:
for x in range(10):
print x
ponieważ jeśli drukować szereg (100) zamiast przedziału (10), czasu zajmie to prowadzony jest 10 razy dłużej. widać bardzo często, że napisany jako O (n), co oznacza, że czas lub obliczeniowa wysiłek, aby uruchomić algorytm jest proporcjonalna do N.
Teraz, powiedzmy, że chcemy wydrukować elementy z dwóch pętli:
for x in range(10):
for y in range(10):
print x, y
Za każde x, przechodzę 10 razy w pętlę y. Z tego powodu cała sprawa przechodzi przez 10x10 = 100 wydruków (możesz je zobaczyć po prostu uruchamiając kod). Jeśli zamiast używać 10, używam 100, teraz metoda zrobi 100x100 = 10000. Innymi słowy, metoda przyjmuje postać O (N * N) lub O (N²), ponieważ za każdym razem, gdy zwiększasz liczbę elementów, wysiłek obliczeniowy lub czas wzrastają jako kwadrat liczby punktów.
Muszą odnosić się do złożoności wykonawczej, nazywanej również notacją Big O. To bardzo duży temat do rozwiązania. Zacznę od artykułu na temat wikipedia: https://en.wikipedia.org/wiki/Big_O_notation
Kiedy badałem ten temat, jedną z rzeczy, których się nauczyłem, jest wykreślenie środowiska wykonawczego mojego algorytmu za pomocą różnych zestawów danych o rozmiarze. Po wykreśleniu wyników zauważysz, że linia lub krzywa może zostać zaklasyfikowana do jednego z kilku porządków wzrostu.
Zrozumienie, w jaki sposób klasyfikować złożoność algorytmu środowiska wykonawczego, daje podstawy do zrozumienia, w jaki sposób algorytm zostanie skalowany pod względem czasu lub pamięci. Da ci to możliwość porównywania i klasyfikowania algorytmów luźno ze sobą.
Nie jestem ekspertem, ale pomogło mi to zacząć od króliczej nory.
Poniżej przedstawione są typowe rzędy wzrostu:
Jeśli artykuł Wikipedii jest trudny do przełknięcia, bardzo polecam obejrzenie wykładów na ten temat na Uniwersytecie iTunes i zajrzenie do tematów analizy algorytmów, notacji big-o, struktur danych, a nawet liczenia operacji.
Powodzenia!
Zazwyczaj spierasz się o algorytm pod względem rozmiaru wejściowego n (jeśli dane wejściowe są tablicą lub listą). Rozwiązaniem liniowym problemu byłby algorytm, którego czasy realizacji skalują się liniowo z n, czyli x*n + y, gdzie x i y są liczbami rzeczywistymi. n pojawia się z najwyższym wykładnikiem 1: n = n^1.
W przypadku rozwiązania kwadratowego, n pojawia się w wyrażeniu z 2 jako najwyższy wykładnik, np. x*n^2 + y*n + z.
Dla arbitralnego n, rozwiązanie liniowe rośnie w czasie wykonywania znacznie wolniej niż kwadratowe.
Aby uzyskać więcej informacji, sprawdź numer Big O Notation.
Nie podałeś, ale jak wspomniałeś o rozwiązaniu, możliwe jest, że pytasz o zbieżność kwadratową i liniową. W związku z tym, jeśli masz algorytmu, który jest iteracyjny i generuje ciąg przybliżeń do wartości zbieżny, to masz kwadratową konwergencję, gdy można wykazać, że
x(n) <= c * x(n-1)^2
jakiegoś pozytywnego stałej c. To znaczy, że błąd w rozwiązaniu w iteracji n+1 jest mniejszy niż kwadrat błędu w iteracji n. Zobacz to, aby uzyskać pełniejszy opis bardziej ogólnych definicji współczynników konwergencji http://en.wikipedia.org/wiki/Rate_of_convergence
Podaję kredyty na tę odpowiedź tylko dlatego, że prosiłem o łatwy sposób wyjaśnienia tego. Ale zdecydowanie wszystkie odpowiedzi są naprawdę miłe i wyczerpujące. –
Należy rozważyć zmianę przykładu na: "dla x w zakresie (n)" tak jak dla x w zakresie (10) jest stały czas, a nie liniowy. – pepper