complexity-theory

20Ciepło

1Odpowiedz

Opis algorytmu Ukkonena dla drzewek przyrostków

Robię trochę pracy z algorytmem Ukkonena do budowania drzewek przyrostków, ale nie rozumiem niektórych części wyjaśnień autora dotyczących jego złożoności w czasie liniowym. Nauczyłem się algorytmu i

164Ciepło

9Odpowiedz

Czy log (n!) = Θ (n · log (n))?

Jestem pokazać, że log (n!) = Θ (n· log (n)). Podpowiedź podano, że należy pokazują górną granicę z nn i wykazują niższe wiązanie z (n/2) (n/2) . Nie wydaje mi się to aż tak intuicyjne. Dlaczego tak s

9Ciepło

4Odpowiedz

Czym jest złożoność dodawania macierzy?

Znalazłem some mentions in another question of matrix addition being a quadratic operation. Ale myślę, że jest liniowy. Jeśli podwoję rozmiar macierzy, muszę obliczyć podwójne dodatki, a nie poczwórne

9Ciepło

1Odpowiedz

Czy są jakieś algorytmy online do testowania płaskości?

Wiem, że można wykonać w O (v) (równoważnie O (e), ponieważ wykresy płaskie mają krawędzie O (v)). Zastanawiam się, czy można to zrobić w trybie online w O (1) czasu amortyzacji, ponieważ każda krawęd

10Ciepło

6Odpowiedz

Narzędzia do analizy złożoności kodu poza złożonością cykliczną

O ile złożoność cykliczna jest wartościową miarą, to uważam ją za słabe narzędzie do identyfikacji trudnego do utrzymania kodu. W szczególności, staram się go znaleźć po prostu podkreśla niektóre rodz

5Ciepło

3Odpowiedz

Big-O złożoność c^n + n * (logn)^2 + (10 * N)^c

potrzebne do uzyskania złożoność Big-O tego wyrażenia: c^n + n * (log (n))^2 + (10 * n)^c gdzie c jest stałą, a n jest zmienną. Jestem prawie pewien, że rozumiem, jak wyprowadzić złożoność Big-O każde

10Ciepło

5Odpowiedz

Czy program bigO algorytmu można znaleźć programowo poprzez analizę jego perfs?

Zauważ, że nie mam "problemu" i nie szukam "innego sposobu na znalezienie dużego O mojego algorytmu". Chciałbym wiedzieć, czy byłoby możliwe napisanie programu, do którego można by przekazywać punkty

9Ciepło

3Odpowiedz

Używa funkcji Ackermanna?

W naszym dyskretnym kursie matematyki na moim uniwersytecie nauczyciel pokazuje swoim studentom Ackermann function i przypisuje uczniowi rozwinięcie funkcji na papierze. Czy oprócz funkcji benchmarkin

7Ciepło

3Odpowiedz

Jak znaleźć pierwszy element zgodnie z konkretnym zamówieniem przy użyciu LINQ w O (n)?

Załóżmy, że mam listę elementów (np. Posty) i chcę znaleźć pierwszy element zgodnie z niektórymi niebanalnymi zamówieniami (np. PublishDate, a następnie CommentCount jako łamacz). Naturalny sposób to

41Ciepło

5Odpowiedz

Co to jest złożoność wykonywania funkcji listy python?

pisałem funkcję Pythona, który wyglądał mniej więcej tak to def foo(some_list): for i in range(0, len(some_list)): bar(some_list[i], i) tak, że został wywołany z x = [0, 1, 2, 3, ... ] f