Czy istnieje złożoność między

10

Czy istnieje stopień złożoności większy niż i mniejszy niż ? $O(n)$ $O(n \log n)$

algorithms complexity efficiency

— użytkownik3696586
źródło

1

Myślę, że może to pytanie lepiej pasowałoby do wymiany stosów informatyki?

— LKlevin

@LKlevin: Zgoda.

— Geoff Oxberry

2

Wymiana stosów informatycznych nie jest zbyt przyjazna dla takich podstawowych pytań.

— Nick Alger,

20

$n \log\log n$ znajduje się między i i jest stosunkowo częstym zjawiskiem na wolności. $n$ $n \log n$

— Bill Barth
źródło

5

Na przykład sito Erasthenos ma złożoność

O (n \log \log n)

$O(n \log \log n)$ .

— Eamon Nerbonne

1

Chociaż w zależności od motywacji pytającego może to nie być istotne rozróżnienie - dla wszystkich praktycznych celów jest tylko małym stałym czynnikiem.

\log \log n

$\log \log n$

— Eamon Nerbonne

2

Tak, choć dotyczy to również jeśli jest wystarczająco małe!

\log n

$\log n$

n

$n$

— Bill Barth

1

@BillBarth Tak, ale jest wykładniczo mniej stała niż

\log \log n

$\log \log n$ !

— Pål GD

7

$O(n\log(\log(n)))$ $O(n \log^*(n))$ $\log^*$

$O(n\log^*(n))$

$\alpha(n,n)$ $O(n\alpha(n,n))$

— Peter Brune
źródło

2

α^{*} (n)

$\alpha^*(n)$

4

$O(n(\log n)^\alpha) \subsetneq O(n(\log n)^\beta)$ $\alpha<\beta$ $O(n) = O(n(\log n)^0) \subsetneq O(n(\log n)^\alpha) \subsetneq O(n\log n)$ $\alpha\in (0,1)$

— David Richerby
źródło