Programowanie big-o

30

Jakie jest proste angielskie wytłumaczenie notacji „Big O”?

Wolałbym jak najmniej formalnej definicji i prostej matematyki.

4934 algorithm complexity-theory computer-science big-o time-complexity

30

Uczę się o czasach działania i czasach amortyzacji Big O Notation. Rozumiem pojęcie czasu liniowego O (n) , co oznacza, że rozmiar danych wejściowych wpływa proporcjonalnie na wzrost algorytmu ... to samo dotyczy na przykład czasu kwadratowego O (n 2 ) itd. Nawet algorytmy , takie jak generatory permutacji, z …

2139 time-complexity big-o

23

Big O, jak to obliczyć / przybliżyć?

Większość osób z dyplomem CS z pewnością wie, co stoi na Big O . Pomaga nam zmierzyć, jak dobrze skaluje się algorytm. Ale jestem ciekaw, w jaki sposób możesz obliczyć lub zbliżenie złożoności algorytmów?

881 algorithm optimization complexity-theory big-o performance

9

Jaka jest różnica między Θ (n) i O (n)?

Czasami widzę Θ (n) z dziwnym symbolem with z czymś pośrodku, a czasem tylko O (n). Czy to tylko lenistwo podczas pisania, ponieważ nikt nie wie, jak wpisać ten symbol, czy oznacza to coś innego?

427 big-o time-complexity notation big-theta

6

Stały amortyzowany czas

Co rozumie się przez „Constant Amortized Time”, gdy mówimy o złożoności czasowej algorytmu?

415 algorithm complexity-theory big-o

4

Lista funkcji Big-O dla PHP

Po dłuższym użyciu PHP zauważyłem, że nie wszystkie wbudowane funkcje PHP działają tak szybko, jak się spodziewano. Rozważ te dwie możliwe implementacje funkcji, która sprawdza, czy liczba jest liczbą pierwszą, używając buforowanej tablicy liczb pierwszych. //very slow for large $prime_array $prime_array = array( 2, 3, 5, 7, 11, 13, .... …

346 php performance algorithm arrays big-o

30

Czy są jakieś algorytmy O (1 / n)?

Czy są jakieś algorytmy O (1 / n)? Lub cokolwiek innego, co jest mniejsze niż O (1)?

335 theory complexity-theory big-o

12

Złożoność obliczeniowa sekwencji Fibonacciego

Rozumiem notację Big-O, ale nie wiem, jak ją obliczyć dla wielu funkcji. W szczególności starałem się zrozumieć złożoność obliczeniową naiwnej wersji sekwencji Fibonacciego: int Fibonacci(int n) { if (n <= 1) return n; else return Fibonacci(n - 1) + Fibonacci(n - 2); } Jaka jest złożoność obliczeniowa sekwencji Fibonacciego i …

330 time-complexity big-o complexity-theory fibonacci

3

Różnica między notacją Big-O i Little-O

Jaka jest różnica między Big-O notacji O(n)i Little-O notacji o(n)?

330 algorithm time-complexity big-o asymptotic-complexity little-o

5

Określanie złożoności funkcji rekurencyjnych (notacja Big O)

Mam jutro informatykę i potrzebuję pomocy w określeniu złożoności tych funkcji rekurencyjnych. Wiem, jak rozwiązywać proste sprawy, ale wciąż staram się nauczyć, jak rozwiązywać te trudniejsze sprawy. To tylko kilka przykładowych problemów, których nie mogłem zrozumieć. Każda pomoc byłaby bardzo mile widziana i bardzo pomogłaby w moich studiach, dziękuję! int …

267 recursion big-o complexity-theory

17

Dodać obiekt do listy w R w zamortyzowanym stałym czasie, O (1)?

Jeśli mam listę R mylist, możesz objdo niej dodać element w następujący sposób: mylist[[length(mylist)+1]] <- obj Ale na pewno jest jakiś bardziej zwarty sposób. Kiedy byłem nowy w R, próbowałem pisać w ten lappend()sposób: lappend <- function(lst, obj) { lst[[length(lst)+1]] <- obj return(lst) } ale oczywiście to nie działa z …

245 r performance list append big-o

22

Czy są jakieś przypadki, w których wolisz algorytm o wyższym stopniu złożoności niż O?

Czy są jakieś przypadki, w których wolisz O(log n)złożoność O(1)czasu niż złożoność czasu? A O(n)może O(log n)? Czy masz jakieś przykłady?

242 algorithm big-o time-complexity

30

Jak znaleźć k-ty największy element w nieposortowanej tablicy o długości nw O (n)?

Uważam, że istnieje sposób na znalezienie k-tego największego elementu w nieposortowanej tablicy o długości n w O (n). A może to „oczekiwane” O (n) lub coś takiego. Jak możemy to zrobić?

220 performance algorithm big-o

9

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

Mam pokazać, że log ( n !) = Θ ( n · log ( n )) . Podano podpowiedź, że powinnam pokazać górną granicę za pomocą n n, a dolną granicę za pomocą ( n / 2) ( n / 2) . Nie wydaje mi się to aż tak intuicyjne. …

218 algorithm math recursion complexity-theory big-o

6

Co dokładnie reprezentuje notacja duża Ө?

Jestem naprawdę zdezorientowany różnicami między dużą notacją O, dużą Omegą i dużą notacją Theta. Rozumiem, że duże O to górna granica, a duża Omega to dolna granica, ale co dokładnie oznacza duże Ө (theta)? Czytałem, że oznacza to ciasne związanie , ale co to znaczy?

179 algorithm computer-science big-o notation big-theta

Pytania otagowane jako big-o