Podaj trzy przypadki kiedy algorytm o złożoności O(N^2) jest lepszym wyborem od algorytmu o złożoności O(N).
- Rejestracja:prawie 11 lat
- Ostatnio:ponad 3 lata
- Postów:459
2
- Kartkówka z programowania w liceum
- w.w. w technikum
- kolokwium na pierwszym roku studiów
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
10
- Złożoność pamięciowa. Można sortować liczby w O(n) ale wymaga to O(k) pamięci gdzie
kto maksymalna liczba. Dla 64bitowych intów nie starczy pamieci :) - Stałe ukryte w notacji O, jw. sortowanie przez zliczanie niby jest O(n) ale w praktyce O(n*k), więc jak liczb jest mało a zakres liczb duzy to będzie to działać wolniej
- Poziom skomplikowania algorytmu? Kontrowersyjne, ale w praktyce kod musi być zrozumiały :) Skomplikowany algorytm w miejscu które nie wymaga optymalizacji czasowej, może zwyczajnie nie mieć sensu, bo utrzymanie będzie kosztowne a zysk żaden.
edytowany 1x, ostatnio: Shalom
- Rejestracja:około 8 lat
- Ostatnio:około 6 godzin
- Postów:4882
0
Dodam jeszcze (pozostaje w mocy, to co napisał @Shalom), że zdanie z mojego poprzedniego postu mozna odwrócić, tzn., algorytmy są asymptotycznie lepsze, od pewnego n, co nie znaczy, że są zawsze lepsze. Ekstremalny przypadek: P = NP, ale algorytm wielomianowy jest z jakąś absurdalnie wielką stałą: n + 1000^1000(!). Wszelkie medale i wieczna chwała gwarantowane, ale praktycznie takie odkrycie zmieni nic.
Let's get real, algorytmy sortowania w bibliotekach standartowych zmieniają między implementacjami, zależnie od wielkości i rodzaju danych; algorytmy mnożenia również - np., przez dużą ilość stałych operacji, algorytm mnożenia Shonhage - Strassen, jest efektywny dopiero dla wielkich liczb.
edytowany 2x, ostatnio: lion137
- Rejestracja:ponad 6 lat
- Ostatnio:2 miesiące
- Postów:688
1
- Kiedy jeden jest zaimplementowany baremetal w asm a drugi w Javie.
- Kiedy chodzi nam o ogrzanie pomieszczenia za pomocą procesora.
- Kiedy dłuższy czas wykonywania zapewnia nam więcej czasu na opier*alanie się w pracy
edytowany 2x, ostatnio: Satanistyczny Awatar
- Rejestracja:około 17 lat
- Ostatnio:4 dni
5
Tak jak powiedział @Shalom czas wykonania to nie jedyny aspekt algorytmu, z innych (poza wymienioną złożonością pamięciową):
- cache friendliness - nawet jeśli notacja
Ojest lepsza dla algorytmu X, to czasem siłą zrobisz więcej niż fancy algorytmami (jeśli masz dużo siły) - algorytm jest on-line czy off-line?
- stabilność algorytmu (czy wynik zależy od kolejności danych na wejściu)
- możliwość zrównoleglenia algorytmu oraz jaki procent pracy można zrównoleglić
- jaka jest struktura danych (ex. sortowanie niemutowalnych list przy użyciu quicksorta to średniawy pomysł)
edytowany 2x, ostatnio: hauleth
Zobacz pozostały 1 komentarz
Racja, poprawiam link.
Jak już jesteśmy przy tym - nie obiło wam się może o gałki oczne porównanie architektur i efektywności algorytmów sortowania na nich?
@Satanistyczny Awatar: ja znam 2 sekwencyjne struktury danych: listy i tablice/wektory, wiec jeśli masz random access to qsort (jeśli stabilność nie jest wymagana) lub co chcesz, jeśli ma być stabilnie, natomiast listy to merge sort.
ta, acz mi chodziło o np. architektury typu RISC - takie a takie algo działa na nim tak, a tak, a CISC - jeszcze inaczej, a na jakichś egzotykach "tak, a tak". Nie dopisałem "procesora". Co naprawiam niniejszym. ;P
Sam zrobiłem porównania: https://github.com/tarsa/SortAlgoBox z tym, że między CPU, a GPU oraz między językami programowania. Nie mam ARMów czy PowerPC do testowania to nie testowałem.
2
Dodam jeszcze: kiedy algorytm O(n^2) jest znacznie prostszy oraz n jest na pewno małe lub i tak kod O(n^2) spełnia wymagania wydajnościowe, bo nie znajduje się na krytycznej ścieżce wydajnościowej. W praktyce budżet w projekcie jest ograniczony i lepiej poświęcić go na optymalizację tych fragmentów kodu, które faktycznie mają znaczenie. Jeśli w wyniku zastąpienia O(n^2) gdzieś przez O(n) czas startu aplikacji skróci się z 5 s do 4,99 s, to raczej nie ma to sensu.
No i druga sprawa, o czym pisał już Shalom - często algorytmy o niższej złożoności mają wyższą stałą. Więc dla małych n może się okazać, że O(n^2) faktycznie jest szybsze od O(n), a O(n) jest szybsze od O(1).
edytowany 1x, ostatnio: Krolik
Albo jak zejście do O(N) wymaga tak porytej implementacji, że sam C'thulhu by się wystraszył. ;)
Shalom