Pytania otagowane jako big-o

Notacja Big-O jest używana do reprezentowania asymptotycznych górnych granic. Opisuje istotną złożoność czasową lub przestrzenną algorytmów. Analiza Big-O zapewnia zgrubne i uproszczone oszacowanie trudności problemu.

Co to jest czas pseudo wielomianowy? Czym różni się od czasu wielomianowego?

Co to jest czas pseudo wielomianowy ? Czym różni się od czasu wielomianowego? Niektóre algorytmy działające w czasie pseudo wielomianowym mają czasy wykonania, takie jak O (nW) (dla problemu plecakowego 0/1 ) lub O (√n) (dla podziału próbnego ); dlaczego to nie liczy się jako czas wielomianowy?

101 algorithm big-o time-complexity

Złożoność czasowa algorytmu Euklidesa

Mam trudności z podjęciem decyzji, jaka jest złożoność czasowa największego wspólnego algorytmu mianownika Euclid. Ten algorytm w pseudokodzie to: function gcd(a, b) while b ≠ 0 t := b b := a mod b a := t return a Wydaje się, że zależy to od a i b . Myślę, …

101 algorithm big-o time-complexity iteration

Jaka jest różnica między dolną granicą a ciasną granicą?

W odniesieniu do tej odpowiedzi , czym jest Theta (mocno związana)? Omega to dolna granica, całkiem zrozumiała, minimalny czas, jaki może zająć algorytm. Wiemy, że Big-O dotyczy górnej granicy, czyli maksymalnego czasu, jaki może zająć algorytm. Ale nie mam pojęcia o Theta.

100 big-o

Czy podstawa dziennika Big O (logn) jest e?

W przypadku struktur danych typu drzewo wyszukiwania binarnego widzę, że notacja Big O jest zwykle oznaczana jako O (logn). Czy z małą literą „l” w logarytmie oznacza to logarytm o podstawie e (n), zgodnie z opisem logarytmu naturalnego? Przepraszam za proste pytanie, ale zawsze miałem problem z rozróżnieniem różnych logarytmów …

97 math binary-tree complexity-theory big-o

Dlaczego złożoność obliczeniowa O (n ^ 4)?

int sum = 0; for(int i = 1; i < n; i++) { for(int j = 1; j < i * i; j++) { if(j % i == 0) { for(int k = 0; k < j; k++) { sum++; } } } } Nie rozumiem, jak kiedy j = …

50 java big-o

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.