Podstawowa złożoność czasu 10 = O (n) - big-o

Mówiąc f = O (g) jest bardzo luźnym analogiem f <= g
Różni się od zwykłego pojęcia z powodu stałej c, więc na przykład 10 n = O (n)

To pochodzi z mojego podręcznika, jak mogę 10n <= n kiedy n jest wyraźnie poniżej 10n na wykresie?

Właśnie zacząłem uczyć się o wielkiej notacji O i jestem kompletnie zagubiony.

Odpowiedzi:

Jest na to dobre wytłumaczenie Dlaczego stała jest zawsze usuwana z dużej analizy O? ale zrzucamy stałe.

Innym sposobem myślenia o tym jest 10nw zasadzie taki sam jak n, jeśli jesteś daleko i n jest bardzo duży, gdy porównasz tę funkcję z innymi funkcjami. n ^ 2 jest w zasadzie takie samo jak 10n ^ 2, gdy porównasz te kwadratowe funkcje z funkcją liniową, od której zaczęliśmy.

niech n = 1 000 000. Następnie n = 1 000 000 i 10 n = 10 000 000. n ^ 2 = 1 000 000 000 000 i 10 n ^ 2 = 10 000 000 000 000

Teraz niech n = 1 000 000 000 000. Następnie n = 1 000 000 000 000 i 10 n = 10 000 000 000 000. n ^ 2 = 1 000 000 000 000 000 000 000 000 i 10 n ^ 2 = 10 000 000 000 000 000 000 000 000 000 000

Gdy n staje się większe, funkcja liniowa z dowolnymstała będzie zbliżać się do wartości n w porównaniu do innych klas funkcji, a funkcja kwadratowa będzie zbliżać się do wartości n ^ 2 w porównaniu do innych klas funkcji.

W naszym przykładzie, gdy n wynosi 1 z milionem zer, który dba o jedno zero więcej w czasie liniowym, ponieważ w czasie kwadratu jest o milion więcej zer.