Pytania otagowane jako time-complexity

Złożoność czasowa algorytmu określa ilość czasu potrzebnego do działania algorytmu jako funkcję rozmiaru danych wejściowych do problemu. Złożoność czasowa algorytmu jest zwykle wyrażana za pomocą notacji dużego O, która eliminuje stałe multiplikatywne i terminy niższego rzędu.

2
Duże O tablic JavaScript
Tablice w JavaScript można bardzo łatwo modyfikować, dodając i usuwając elementy. To nieco maskuje fakt, że większość tablic językowych ma stały rozmiar i wymaga skomplikowanych operacji, aby zmienić rozmiar. Wygląda na to, że JavaScript ułatwia pisanie słabo działającego kodu tablicowego. To prowadzi do pytania: Jakiej wydajności (pod względem dużej złożoności …
4
Złożoność czasowa algorytmu Sieve of Eratostenes
Z Wikipedii: Złożoność algorytmu to O(n(logn)(loglogn))operacje bitowe. Jak do tego doszedłeś? To, że złożoność obejmuje ten loglogntermin, mówi mi, że sqrt(n)gdzieś jest. Załóżmy, że uruchamiam sito na pierwszych 100 liczbach ( n = 100), zakładając, że oznaczenie liczb jako złożonych zajmuje stały czas (implementacja tablicy), liczba razy, której użyjemy, mark_composite()byłaby …
4
Czy złożoność czasowa iteracyjnego łańcucha jest faktycznie dołączana O (n ^ 2), czy O (n)?
Pracuję nad problemem z CTCI. Trzeci problem z rozdziału 1 polega na tym, że bierzesz ciąg, taki jak 'Mr John Smith ' i prosi o zastąpienie spacji pośrednich %20: 'Mr%20John%20Smith' Autor oferuje takie rozwiązanie w Pythonie, nazywając je O (n): def urlify(string, length): '''function replaces single spaces with %20 and …
2
Javascript ES6 złożoność obliczeniowa / czasowa zbiorów
Jaką złożoność czasową (w notacji duże-O) zapewnia specyfikacja ES6 dla kolekcji z kluczem (Set, Map, WeakSet i WeakMap)? Oczekuję, i spodziewam się tego od większości programistów, że specyfikacje i implementacje będą używać powszechnie akceptowanych algorytmów wydajności, w którym to przypadku Set.prototype.has, addi deletewszystkie będą O (1) w przeciętnym przypadku. To …
12
Sortowanie w informatyce a sortowanie w „prawdziwym” świecie
Myślałem o sortowaniu algorytmów w oprogramowaniu i możliwych sposobach pokonania O(nlogn)przeszkody. Nie sądzę, że w praktyce możliwe jest szybsze sortowanie, więc proszę, nie myśl, że tak. Mając to na uwadze, wydaje się, że w przypadku prawie wszystkich algorytmów sortowania oprogramowanie musi znać położenie każdego elementu. Co ma sens, w przeciwnym …
1
Jaka jest złożoność czasowa różnych struktur danych?
Próbuję wymienić czasową złożoność operacji wspólnych struktur danych, takich jak tablice, drzewo wyszukiwania binarnego, sterta, lista połączona itp., A zwłaszcza mam na myśli Javę. Są bardzo częste, ale wydaje mi się, że niektórzy z nas nie są w 100% pewni dokładnej odpowiedzi. Każda pomoc, zwłaszcza referencje, jest bardzo mile widziana. …
5
Najgorszy przypadek w Max-Heapify - jak uzyskać 2n / 3?
W CLRS, wydanie trzecie, na stronie 155 podano, że w MAX-HEAPIFY, Każde poddrzewo dziecięce ma rozmiar co najwyżej 2n / 3 - najgorszy przypadek ma miejsce, gdy dolny poziom drzewa jest dokładnie w połowie zapełniony. Rozumiem, dlaczego jest najgorzej, gdy dolny poziom drzewa jest wypełniony dokładnie do połowy. W tym …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.