Czy ktoś może wskazać mi źródło zawierające listę złożoności Big-O podstawowych funkcji bibliotecznych clojure, takich jak conj, cons itd.? Wiem, że Big-O różni się w zależności od rodzaju danych wejściowych, ale czy jest dostępny taki zasób? Czuję się niekomfortowo, kodując coś, nie mając pojęcia, jak szybko to się skończy.Funkcje Big O z biblioteki clojure
Oto tabela składa się John Jacobsen i podjęte from this discussion:
późno do partii tutaj, ale znalazłem the link in the comments of the first answer być bardziej ostateczne, więc jestem przeksięgowanie go tutaj z kilkoma modyfikacjami (to znaczy, english->big-o)
W kolekcjach nieposortowanych, O (log n) jest prawie stały czas, a ponieważ 2 węzłów może zmieścić się w węzłach podzielonych na bity trie, oznacza to worst-case complexity of log32232 = 6.4. Wektory są również tries where the indices are keys.
Posortowane kolekcje wykorzystują wyszukiwanie binarne tam, gdzie to możliwe. (Tak, są to zarówno technicznie O (log n), w tym stały współczynnik służy jako odniesienie.)
Listy gwarantują stały czas operacji dla pierwszego elementu i O (n) dla wszystkich pozostałych.
"1" w cudzysłowie, jest tak blisko, że nie ma znaczenia (według Rich Hickey.) Ale tak naprawdę jest O (log_32 głębokość)? –
Ta tabela nie jest całkowicie poprawna. "last" jest zawsze O (n). 'cons' jest zawsze O (1) (zakładając, że' seq' jest zawsze O (1)). 'conj' w wektorze to tylko" 1 ", a nie 1. – kotarak
@kotarak Czy byłbyś w stanie trochę poprawić swoje poprawki? :) – Anonymous