Kas yra paprastas „Big O“ anglų kalbos paaiškinimas?

Norėčiau, kad būtų kuo mažiau formalios apibrėžties ir paprastos matematikos.

4660
28 янв. Arec Barrwin nustatė sausio 28 d 2009-01-28 14:10 '09, 14:10, 2009-01-28 14:10
@ 39 atsakymų
  • 1
  • 2

Greita pastaba, ji beveik neabejotinai supainioja Big O žymėjimą (kuris yra viršutinė riba) su pavadinimu Theta (kuris yra dvipusis). Mano patirtis rodo, kad tai būdinga diskusijoms ne akademinėmis sąlygomis. Atsiprašome už bet kokią painiavą.


Su šiuo grafiku galite vizualizuoti „Big O“ sudėtingumą:

2019

6267
28 янв. Atsakymas yra suteiktas klastotė sausio 28 2009-01-28 14:18 '09 14:18 2009-01-28 14:18

Rodo algoritmo mastelio keitimą.

O (n 2 ) : žinomas kaip kvadratinis sudėtingumas

  • 1 elementas: 1 sekundė
  • 10 elementų: 100 sekundžių
  • 100 elementų: 10 000 sekundžių

Atkreipkite dėmesį, kad elementų skaičius padidėja 10 kartų, tačiau laikas padidėja 10 kartų 2 . Iš esmės n = 10, todėl O (n 2 ) suteikia mums skalės koeficientą n 2, kuris yra 10 2 .

O (n) : žinomas kaip linijinis kompleksas

  • 1 elementas: 1 sekundė
  • 10 elementų: 10 sekundžių
  • 100 elementų: 100 sekundžių

Šį kartą elementų skaičius padidėja 10 kartų, taip pat ir laikas. n = 10, todėl skalės koeficientas O (n) yra 10.

O (1) : žinomas kaip pastovus sudėtingumas

  • 1 elementas: 1 sekundė
  • 10 taškų: 1 sekundė
  • 100 vienetų: 1 sekundė

Elementų skaičius vis dar didėja 10 kartų, tačiau skalės koeficientas O (1) visada yra 1.

O (log n) : žinomas kaip logaritminis sudėtingumas

  • 1 elementas: 1 sekundė
  • 10 elementų: 2 sekundės
  • 100 elementų: 3 sekundės
  • 1000 elementų: 4 sekundės
  • 10 000 vienetų: 5 sekundės

Skaičiavimų skaičius padidinamas tik įvesties vertės žurnalu. Todėl tokiu atveju, jei kiekvienas skaičiavimas trunka 1 sekundę, įvesties log n yra reikalingas laikas, todėl log n .

Tai yra jos esmė. Jie mažina matematiką, todėl jis gali būti ne lygus n 2 ar bet koks, bet tai bus pagrindinis mastelio keitimo veiksnys.

682
28 янв. Ray Hidayat atsakymas sausio 28 d 2009-01-28 14:28 '09, 14:28, 2009-01-28 14:28

Didelis O žymėjimas (taip pat vadinamas „asimptotiniu augimu“) yra tai, kaip atrodo funkcijos, kai ignoruojate nuolatinius veiksnius ir pan. Mes naudojame tai, kad galėtume kalbėti apie tai, kaip viskas keičiama .


pagrindai

už „pakankamai“ didelių sąnaudų ...

  • f(x) ∈ O(upperbound) reiškia, kad f "neauga greičiau nei" upperbound
  • f(x) ∈ Ɵ(justlikethis) reiškia, kad f "auga kaip" justlikethis
  • f(x) ∈ Ω(lowerbound) reiškia, kad f "auga ne lėčiau nei" lowerbound

Didelis O žymėjimas 9x² pastoviais veiksniais: 9x² , kad 9x² funkcija „auga lygiai kaip“ 10x² . Big-O asimptotinė notacija taip pat nerūpi ne asimptotiniais dalykais („arti šaltinio“ ar „kas atsitinka, kai problemos dydis yra mažas“): 10x² , kad funkcija 10x² „auga lygiai taip, kaip“ 10x² - x + 2 .

Kodėl norite ignoruoti mažesnes lygtis? Kadangi didelės ir didelės skalės yra didelės dalies lygtys, jos labai užgožtos; jų indėlis tampa nykštukė ir nereikšminga. (Žr. Pavyzdžio skyrių.)

Kitaip tariant, viskas priklauso nuo santykio, kai artėja prie begalybės. Jei padalijote faktinį laiką, kurį reikia į O(...) , jūs gaunate pastovų veiksnį didelių įėjimų ribose. Intuityviai, tai prasminga: funkcijos „skalės kaip“ viena kitai, jei galite daugintis, kad gautumėte kitą. Tai yra, kai mes sakome ...

 actualAlgorithmTime(N) ∈ O(bound(N)) eg "time to mergesort N elements is O(N log(N))" 

... tai reiškia, kad „pakankamai didelių“ problemų N dydžių (jei ignoruojame daiktus šalia kilmės), yra tam tikras konstanta (pavyzdžiui, 2.5, visiškai sudaryta), kad:

 actualAlgorithmTime(N) eg "mergesort_duration(N) " ────────────────────── < constant ───────────────────── < 2.5 bound(N) N log(N) 

Yra daug galimybių konstantoms; dažnai „geriausias“ pasirinkimas yra žinomas kaip „nuolatinis algoritmo faktorius“, bet dažnai tai ignoruojame, nes mes nepaisome didžiausių terminų (žr. skyrių „Nuolatiniai veiksniai“, kodėl jie paprastai neturi reikšmės). Pirmiau minėtą lygtį taip pat galite peržiūrėti kaip suvaržymą, sakydami: „Blogiausiu atveju laikas, kurio jis užtruks, niekada nebus blogesnis nei apie N*log(N) , kurio koeficientas yra 2,5 (pastovus veiksnys, dėl kurio mes nerūpi) ".

Apskritai, O(...) yra naudingiausia, nes dažnai rūpinamės elgesiu blogiausiu atveju. Jei f(x) reiškia kažką „blogo“, pvz., Procesoriaus ar atminties naudojimo, „ f(x) ∈ O(upperbound) “ reiškia „ upperbound - blogiausio atvejo procesoriaus / atminties naudojimo scenarijų“.


Programos

Kaip tik matematinė konstrukcija, didelis-O žymėjimas neapsiriboja kalbėjimo apie apdorojimo laiką ir atmintį. Galite tai naudoti, norėdami aptarti asimptotinius dalykus, kai yra prasmingas mastelio keitimas, pavyzdžiui:

  • galimų rankų paspaudimų tarp N žmonių skaičius partijoje ( Ɵ(N²) , ypač N(N-1)/2 , bet svarbu, kad jis būtų „svarstyklės kaip
  • tikėtinas tikėtinas žmonių skaičius, kurie laiko tam tikrą virusinę rinkodarą kaip laiko funkcija
  • kaip svetainės latentinė skalė su procesoriaus blokų skaičiumi CPU, GPU arba kompiuterių klasteryje
  • kaip procesoriaus šiluminė galia miršta priklausomai nuo tranzistorių, įtampos ir pan.
  • kiek laiko algoritmas turi veikti, priklausomai nuo įvesties dydžio
  • kiek vietos turite paleisti algoritmą, priklausomai nuo įvesties dydžio

pavyzdys

Pirmiau minėtam rankų paspaudimo pavyzdžiui, kiekvienas kambaryje kratomas rankas. Šiame pavyzdyje #handshakes ∈ Ɵ(N²) . Kodėl?

Valgykime truputį: rankų paspaudimų skaičius yra lygus n-select-2 arba N*(N-1)/2 (kiekvienas N žmogus pakrato vienas kito rankas N-1, tačiau tai yra dvigubai didesnė nei ranka), todėl padalinkite iš 2):

Tačiau labai dideliam žmonių skaičiui linijinis narys N tampa mažesnis ir efektyviai prideda 0 santykiui (diagramoje: tuščių blokų dalis įstrižai, palyginti su bendru blokų skaičiumi, mažėja dalyvių skaičiui). Taigi, order N² arba rankų paspaudimų skaičius „auga kaip N²“.

 #handshakes(N) ────────────── ≈ 1/2 N² 

Kaip ir diagramos įstrižainėje nėra net tuščių laukų (N * (N-1) / 2 žymės) (asimptotiniu būdu N 2 žymės).

(laikinas nukrypimas nuo „paprasto anglų“) :) Jei norite tai įrodyti sau, galite atlikti keletą paprastų santykių algebrų, kad jį lim į keletą terminų ( lim reiškia „laikoma lim “, tiesiog ignoruokite, jei to nepastebėjote) tai tik „ir N yra labai didelis“ pavadinimas):

  N²/2 - N/2 (N²)/2 N/2 1/2 lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2 N→∞ N² N→∞ N² N² N→∞ 1 ┕━━━┙ this is 0 in the limit of N→∞: graph it, or plug in a really large number for N 

tl; dr: rankų paspaudimų skaičius atrodo „x² didelėms reikšmėms taip, kad jei įrašysime # rankos paspaudimų / x² santykį, tai, kad mums nereikia x² rankų paspaudimų, netgi netyčia ilgai neišreikštų dešimtainiu pavidalu.

Pavyzdžiui, x = 1 mln., santykis # handshaking / x²: 0.499999 ...


Statyti intuiciją

Tai leidžia mums padaryti tokius pareiškimus kaip ...

"Kad būtų pakankamai didelis įvesties dydis = N, nesvarbu, koks yra pastovus faktorius, jei dvigubai įvesties dydį ...

  • ... Aš dvigubinu laiką, praleistą O (N) algoritmu ("linijinis laikas"). "

    N → (2N) = 2 ( N )

  • ... Dukart kvadratinį (keturis kartus) laiką, praleistą O (N²) algoritmu ("kvadratinis laikas"). "(Pavyzdžiui, 100x užduotis, kaip didelė, užima 100² = 10000x, kiek ilgai ... galbūt nestabili)

    → (2N) ² = 4 ( )

  • ... Aš padvigubinsiu (aštuonkampyje) kubo (O³) algoritmo („kubinio laiko“) laiką. "(Pavyzdžiui, 100x užduotis, kaip didelė, užima 100³ = 1000000x, kiek laiko ... labai nestabili)

    cN³ → c (2N) ³ = 8 ( cN³ )

  • ... Aš pridedu fiksuotą sumą iki laiko, kai jis ima O (log (N)) algoritmą ("logaritminis laikas"). "(Pigūs!)

    c log (N) → c log (2N) = (c log (2)) + ( c log (N) ) = (fiksuota suma) + ( c log (N) )

  • ... Aš nekeičiu laiko O (1) algoritmo ("pastovus laikas"). "(Pigiausia!)

    c * 1c * 1

  • ... I "(iš esmės) dvigubai laiko, kurį laiko O (N log (N)) algoritmas. "(Dažnai)

    jis yra mažesnis nei O (N 1.000001 ), kurį jūs vadinate iš esmės linijiniu

  • ... Aš juokingai didinu laiką, praleistą O (2 N ) algoritmu ("eksponentinis laikas"). „(Jūs dvigubai (arba trigubai ir tt) laikas), tiesiog padidinkite problemą vienu

    2 N → 2 2N = (4 N ) ............ kitaip tariant ...... 2 N → 2 N + 1 = 2 N 2 1 = 2 2 N

[matematiškai linkę, galite perkelti spoilerius į mažesnius ženklus]

(ačiū už ngn-wiki.ru.site/questions/89 / ... )

(techniškai pastovus veiksnys gali kilti kai kuriuose labiau ezoteriniuose pavyzdžiuose, bet aš suformulavau pirmiau (pavyzdžiui, žurnale (N)), kad taip nėra)

Tai augimo salės, kurias programuotojai ir taikomieji kompiuterių mokslininkai naudoja kaip atskaitos taškus. Jie visą laiką mato. (Todėl, nors ir techniškai manote: „Padvigubinus įvestį, O (√N) algoritmas 1414 kartų sulėtėja,“ geriau tai galvoti, nes „tai yra blogiau nei logaritminė, bet geriau nei linijinė“.)


Nuolatiniai veiksniai

Обычно нас не волнуют конкретные константные факторы, потому что они не влияют на то, как растет функция. Например, два алгоритма могут занять O(N) время для завершения, но один может быть в два раза медленнее, чем другой. Нас, как правило, не волнует слишком много, если фактор не очень велик, так как оптимизация - непростая задача ( когда оптимизация преждевременна? ); Кроме того, простое действие выбора алгоритма с лучшим значением big-O часто повышает производительность на порядки.

Некоторые асимптотически превосходные алгоритмы (например, сортировка без сравнения O(N log(log(N))) ) могут иметь такой большой постоянный коэффициент (например, 100000*N log(log(N)) ) или относительно большие издержки как O(N log(log(N))) со скрытыми + 100*N , которые их редко стоит использовать даже для "больших данных".


Почему O (N) иногда лучшее, что вы можете сделать, то есть, почему нам нужны структуры данных

O(N) алгоритмы в некотором смысле являются "лучшими" алгоритмами, если вам нужно прочитать все ваши данные. Сам акт чтения группы данных является операцией O(N) . Загрузка его в память обычно выполняется за O(N) (или быстрее, если у вас есть аппаратная поддержка, или вообще без времени, если вы уже прочитали данные). Однако, если вы дотронетесь или даже посмотрите на каждый фрагмент данных (или даже на любой другой фрагмент данных), вашему алгоритму потребуется O(N) время, чтобы выполнить этот поиск. Не важно, сколько времени займет ваш фактический алгоритм, он будет по крайней мере O(N) потому что он потратил это время на просмотр всех данных.

То же самое можно сказать и о самом акте письма . Все алгоритмы, которые распечатывают N вещей, будут занимать N времени, потому что выходной результат, по крайней мере, такой длинный (например, распечатка всех перестановок (способов перестановки) набора из N игральных карт является факториальной: O(N!) ).

Это мотивирует использование структур данных : структура данных требует чтения данных только один раз (обычно O(N) время), плюс некоторое произвольное количество предварительной обработки (например, O(N) или O(N log(N)) или O(N²) ) который мы стараемся держать маленьким. После этого изменение структуры данных (вставки/удаления/и т.д.) И выполнение запросов к данным занимают очень мало времени, например, O(1) или O(log(N)) . Затем вы приступаете к выполнению большого количества запросов! В целом, чем больше работы вы готовы выполнить раньше времени, тем меньше работы вам придется выполнять позже.