Poszukuje jakikolwiek algorytm który jest opisywany przez złozonosc obliczenia logarytmiczna O(n)= logn.
Najlepiej wzbogacony o jego analize, prosze o pomoc, zaleza od tego moja studia..****
0
0
Nie wiem co to niby jest O(n)= logn. Moze chodziło ci po prostu o O(logn)? Takich algorytmów jest cała masa, choćby szukanie połówkowe, dość trywialne w analizie.
https://en.wikipedia.org/wiki/Binary_search_algorithm#Performance
1
Swoją drogą, to pytanie jest trudniejsze niż się wydaje. Wyszukiwanie połówkowe, wyszukiwanie w drzewie itp. mają złożoność logarytmiczną tylko jeśli się przyjmie pewną uproszczoną wizję świata nauczaną w szkole na uczelni. Niestety nieprawdziwą:
http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-part-i
http://www.ilikebigbits.com/blog/2014/4/28/the-myth-of-ram-part-ii
http://www.ilikebigbits.com/blog/2014/4/29/the-myth-of-ram-part-iii
Ktoś może uważać,że to tylko takie tam filozoficzne rozważania, ale przez to w praktyce algorytm liczenia unikatowych elementów kolekcji za pomocą sortowania ma lepszą złożoność asymptotyczną O(n log n) niż algorytm eliminacji duplikatów za pomocą tablicy z haszowaniem O(n sqrt(n)) i jest szybszy dla każdego N, totalnie wbrew intuicji i wbrew obiegowym mądrościom ze StackOverflow.
Znacie jakieś algorytmy prawdziwie O(log n)?
2
@Krolik nie mylmy pojęć tutaj. Czy innym jest abstrakcyjne/matematyczne pojęcie rzędu złożonosci obliczeniowej algorytmu, a zupełnie czym innym jest praktyczna realizacja! Zauważ ze licząc rząd złożoności obliczeniowej algorytmu robi sie to przy założeniu stałego kosztu pewnych operacji wiodących i przy tym założeniu jest to jak najbardziej poprawne. I nie chodzi tu o żadna "uproszczoną wizję" tylko o przyjęte definicje.
W praktyce to każdy algorytm się robi wykładniczy jak tylko usuniemy ograniczenia na rozmiar liczb ;) No bo głupie porównanie dwóch liczb to ma koszt stały co najwyżej jak te liczby wejdą do rejestrów CPU. Ale jeśli mogłyby mieć nieograniczony rozmiar to samo ich porównanie staje się nagle liniowe względem liczby bitów.
O realizacji praktycznej to w ogóle nie ma co mówić, bo tam czasy wykonywania operacji mogą rożnić się o rzędy wielkości ;)
1
Zauważ ze licząc rząd złożoności obliczeniowej algorytmu robi sie to przy założeniu stałego kosztu pewnych operacji wiodących i przy tym założeniu jest to jak najbardziej poprawne.
Zgadzam się. Wskazałem tylko, że te założenia są dość uproszczone / nierealne i mogą prowadzić do wniosków niemożliwych do uzyskania w praktyce, i że można je ustanowić inaczej, a wtedy zmieniają się "wyniki". Przyjęcie pierwiastkowego czasu dostępu do pamięci oraz uwzględnienie logarytmicznego wzrostu liczby bitów z wielkością liczb jest znacznie dokładniejszym modelem teoretycznym do porównywania algorytmów, choć oczywiście trochę trudniejszym w obliczeniach.
0
Najlepszy przykład to heap (kopiec) w którym bardzo często występuje taka złożoność operacji.