Ką reiškia O (log n)?

Šiuo metu studijuoju „Big O Notation“ vykdymo laiką ir nusidėvėjimo laiką. Suprantu linijinio laiko O (n) sąvoką, o tai reiškia, kad įvesties dydis turi įtakos algoritmo augimui proporcingai ... ir tas pats taikoma, pavyzdžiui, kvadratiniam O (n 2 ) ir kt. net algoritmai, tokie kaip permutacijos generatoriai, kurių O (n!) laikai auga faktiškai.

Pavyzdžiui, ši funkcija yra O (n), nes algoritmas auga proporcingai jo įvesties n:

 f(int n) { int i; for (i = 0; i < n; ++i) printf("%d", i); } 

Panašiai, jei būtų įdėta kilpa, laikas būtų O (n 2 ).

Bet kas yra O (log n)? Pavyzdžiui, ką reiškia pasakyti, kad pilno dvejetainio medžio aukštis yra O (log n)?

Žinau (galbūt ne labai išsamiai), kas logaritmas yra ta prasme, kad: log 10 100 = 2, bet aš negaliu suprasti, kaip atpažinti funkciją logaritminiu laiku.

1737 m
21 февр. nustatė Andreas Grech , vasario 21 d. 2010-02-21 23:05 '10, 11:05 PM 2010-02-21 23:05
ответ 31 atsakymų
  • 1
  • 2

Aš negaliu išsiaiškinti, kaip apibrėžti funkciją su žurnalo laiku.

Dažniausiai logaritminės vykdymo funkcijos atributai yra:

  • pasirenkant kitą elementą, kuriam atlikti veiksmą, yra viena iš kelių galimybių, ir
  • reikia pasirinkti tik vieną.

arba

  • elementai, kuriais atliekamas veiksmas, yra skaitmenys n

Todėl, pavyzdžiui, žmonių paieška telefonų knygoje yra O (log n). Jums nereikia patikrinti kiekvieno telefono knygos asmens, kad rastumėte tinkamą; vietoj to galite paprasčiausiai suskirstyti ir užkariauti, kai jų vardas yra abėcėlės tvarka, ir kiekviename skyriuje jums reikia tik ištirti kiekvienos sekcijos pogrupį, kol galiausiai surasite telefono numerį.

Žinoma, didelė telefonų knyga vis dar užtruks ilgiau, tačiau ji nepadidės taip greitai, kaip proporcingas papildomo dydžio padidėjimas.


Mes galime išplėsti pavyzdinę telefonų knygą, kad palygintume kitų rūšių operacijas ir jų darbo valandas. Manome, kad mūsų telefonų knygoje yra įmonių („geltonųjų puslapių“), turinčių unikalių vardų ir žmonių („baltųjų puslapių“), kuriuose gali būti unikalių pavadinimų. Telefono numeris priskirtas ne daugiau kaip vienam asmeniui ar įmonei. Taip pat darome prielaidą, kad tam tikrame puslapyje eina pastovus laikas.

Štai keletas operacijų, kurias galėtume atlikti telefonų knygoje, nuo geriausių iki blogiausių:

  • O (1) (geriausias variantas): puslapyje, kuriame yra įmonės pavadinimas ir įmonės pavadinimas, suraskite telefono numerį.

  • O (1) (vidurinis korpusas): puslapyje, kuriame yra asmens vardas ir pavardė, suraskite telefono numerį.

  • O (log n): atsižvelgiant į asmens vardą, suraskite telefono numerį, pasirinkdami atsitiktinį tašką, maždaug pusę tos knygos dalies, kurios neradote, tada patikrinkite, ar asmens vardas yra tuo momentu. Tada pakartokite procesą maždaug per pusę per knygos dalį, kurioje yra asmens vardas. (Tai binarinė asmens vardo paieška.)

  • O (n): suraskite visus žmones, kurių telefono numeriuose yra numeris „5“.

  • O (n): atsižvelgiant į telefono numerį, suraskite asmenį ar verslą šiuo numeriu.

  • O (n log n): spausdintuvo biure buvo susijaudinimas, o visi jo puslapiai buvo įtraukti į mūsų telefonų knygą atsitiktine tvarka. Ištaisykite užsakymą taip, kad jis būtų pataisytas, peržiūrint kiekvieno puslapio pirmąjį vardą ir tada įdėkite šį puslapį į naują vietą tuščioje telefonų knygoje.

Toliau pateikti pavyzdžiai yra spausdintuvo biure. Telefonų knygos laukia, kol jos bus išsiųstos kiekvienam gyventojui ar verslui, ir kiekvienoje telefonų knygoje bus lipdukas, kuriame nurodoma, kur jis turi būti išsiųstas. Kiekvienas asmuo ar verslas gauna vieną telefonų knygą.

  • O (n log n): norime individualizuoti telefonų knygą, todėl ketiname surasti kiekvieną asmenį ar įmonės pavadinimą savo paskirtoje kopijoje, tada apvažiuoti savo vardą knygoje ir parašyti trumpą padėką už jų globą,

  • O (n 2 ): Tarnyboje įvyko klaida, o kiekvienos telefono knygos įrašai turi papildomą „0“ telefono numerio pabaigoje. Paimkite baltą ir pašalinkite kiekvieną nulį.

  • O (n · n!): Esame pasirengę įkelti telefono knygas į doką. Deja, robotas, kuris turėjo įkelti knygas, suklupo: knygas ant sunkvežimio padėjo atsitiktine tvarka! Dar blogiau, jis įkelia visas knygas į sunkvežimį ir tada patikrina, ar jos yra teisinga tvarka, ir jei ne, jis juos iškrauna ir pradeda. (Tai yra siaubingas Dievo tipas .)

  • O (n n ): pataisote robotą taip, kad jis teisingai įkrautų daiktus. Kitą dieną vienas iš jūsų darbuotojų atlieka pokštą ir užrašo roboto įkėlimą į automatizuotas spausdinimo sistemas. Kiekvieną kartą, kai robotas įkelia originalią knygą, gamyklinis spausdintuvas kopijuoja visas telefono knygas! Laimei, robotų klaidų aptikimo sistemos yra pakankamai sudėtingos, kad robotas nesistengia spausdinti dar daugiau kopijų, kai jis atsisiunčia dublikato knygą, tačiau vis tiek turi atsisiųsti kiekvieną originalą ir pasikartojančią knygą.

2188
21 февр. atsakymą pateikė John Feminella vasario 21 d. 2010-02-21 23:14 '10, 23:14, 2010-02-21 23:14

O(log N) iš esmės reiškia, kad laikas eina tiesiškai ir n eksponentiškai. Todėl, jei skaičiuojant 10 užtrunka 2 sekundė, reikia skaičiuoti 100 sekundžių ( 1000 sekundžių) skaičiuoti 2 sekundes ( 3 sekundes) ir pan.

Tai yra O(log N) kai skirstome ir valdome algoritmų tipą, pvz., Dvejetainę paiešką. Kitas pavyzdys yra greitas rūšiavimas, kur kiekvieną kartą mes padalinę masyvą į dvi dalis ir kiekvieną kartą, kai reikia rasti O(N) laiką, kad rastume lankstymo elementą. Todėl NO(log N)

466
21 февр. atsakymas pateikiamas greitas kodai 21 vasaris. 2010-02-21 23:18 '10, 11:18 PM 2010-02-21 23:18

Toliau pateikiamame paaiškinime naudojamas visiškai subalansuoto dvejetainio medžio atvejis, padedantis suprasti, kaip gauname logaritminį laiko sudėtingumą.

Dvejetainis medis yra atvejis, kai n dydžio problema yra padalyta į n / 2 dydžio užduotį, kol pasiekiame 1 dydžio problemą:

2019

26 окт. atsakymą pateikė 2cupsOfTech 26 spalis 2012-10-26 22:33 '12, 10:33 pm 2012-10-26 22:33

Jei turite funkciją, kuri priima:

 1 millisecond to complete if you have 2 elements. 2 milliseconds to complete if you have 4 elements. 3 milliseconds to complete if you have 8 elements. 4 milliseconds to complete if you have 16 elements. ... n milliseconds to complete if you have 2**n elements. 

Tada reikia log 2 (n) laiko. Ženklas „ Big O“, laisvai kalbantis, reiškia, kad santykiai turi būti tik dideli n, o pastovūs veiksniai ir mažesni terminai gali būti ignoruojami.

121
21 февр. Mark Byers atsakymas vasario 21 d 2010-02-21 23:11 '10, 23:11, 2010-02-21 23:11

Peržiūra

Kiti pateikė gerus diagramų pavyzdžius, pavyzdžiui, medžio diagramas. Aš nemačiau paprastų kodų pavyzdžių. Todėl, be mano paaiškinimo, pateiksiu keletą algoritmų su paprastais spausdinimo pareiškimais, kad būtų galima paaiškinti įvairių algoritmų kategorijų sudėtingumą.

Pirmiausia norėsite turėti bendrą logaritmo idėją, kurią galite gauti iš https://en.wikipedia.org/wiki/Logarithm . Gamtos mokslai naudoja e ir natūralų žurnalą. Inžinerijos studentai naudos log_10 (duomenų bazės bazę 10), o kompiuterių mokslininkai daug naudos log_2 (2 bazės bazę), nes kompiuteriai yra pagrįsti dvejetainiu kodu. Kartais matote natūralius žurnalo santrumpas kaip ln() , inžinieriai paprastai palieka _10 ir tiesiog naudoja log() , o log_2 sutrumpinamas kaip lg() . Visi logaritmų tipai auga panašiai, todėl jie turi tą pačią log(n) kategoriją log(n) .

Žiūrėdami žemiau pateiktus kodo pavyzdžius, rekomenduoju žiūrėti į O (1), tada O (n), tada O (n ^ 2). Pažvelkite į kitus ir būkite malonūs. Įtraukiau grynus pavyzdžius, taip pat parinktis, rodančias, kaip subtilūs pakeitimai vis dar gali lemti tą patį klasifikavimą.

Galite galvoti apie O (1), O (n), O (logn) ir kt. kaip klasės ar augimo kategorijos. Kai kurioms kategorijoms reikės daugiau laiko nei kiti. Šios kategorijos padeda racionalizuoti algoritmo veikimą. Kai kurie išaugo greičiau, nes n išaugo. Toliau pateiktoje lentelėje parodyta skaičiuoti augimas. Žemiau esančioje lentelėje mes laikome žurnalą (n) kaip log_2 viršutinę ribą.

2019

27 апр. James Oravec atsakymas balandžio 27 d 2016-04-27 01:50 '16 at 1:50 2016-04-27 01:50

Logaritminis veikimo laikas ( O(log n) ) iš esmės reiškia, kad darbo laikas auga proporcingai įvesties dydžio logaritmui - pavyzdžiui, jei 10 elementų užima ne daugiau kaip x laiko ir 100 vienetų, daugiausia, ty, 2x , ir 10 000 elementai užima ne daugiau kaip 4x , tada atrodo, kad laiko O(log n) sudėtingumas.

84
atsakymas pateikiamas anon. Vasario 21 d 2010-02-21 23:10 '10, 23:10, 2010-02-21 23:10

Logaritmas

Na, pabandykime visiškai suprasti, kas yra logaritmas.

Įsivaizduokite, kad mes turime virvę, ir mes ją susiejome su arklu. Jei lynas yra tiesiogiai susietas su arklu, jėga, kurią arklys turi traukti (tarkim, iš asmens), bus tiesus 1.

Dabar įsivaizduokite, kad virvė yra susukta aplink polį. Arkliai, norėdami eiti, dabar turi daug kartų traukti. Kelių kartų skaičius priklausys nuo lyno šiurkštumo ir poliaus dydžio, bet leiskite daryti prielaidą, kad ji daugina vieną jėgą 10 (kai virvė sukasi visą posūkį).

Dabar, jei virvė vieną kartą užsidaro, arklys turės būti ištrauktas 10 kartų sunkiau. Jei žmogus nusprendžia, kad tai tikrai sunku žirgui, jis vėl gali pasukti virvę aplink polį, dar 10 kartų padidindamas savo jėgą. Trečiasis ciklas vėl padidins jėgą dar 10 kartų.

2019

08 окт. atsakymas pateikiamas gudthing 08 oct. 2016-10-08 17:27 '16 at 17:27 pm 2016-10-08 17:27

Galite pagalvoti apie O (log N) intuityviai, sakydamas, kad laikas yra proporcingas skaičių skaičiui N.

Jei operacija atlieka pastovų darbo laiką kiekviename skaitmenyje arba įvesties bituose, visa operacija užtruks proporcingai įvesties skaitmenų arba bitų skaičiui, o ne įvesties vertei; taigi, O (log N), o ne O (N).

Jei operacija priima sprendimus dėl laiko konstantos, kurių kiekviena pusė (sumažina 3, 4, 5 ...), bus atsižvelgiama į įvesties signalo dydį, kuris bus svarstomas, visas užtruks laiko, proporcingo logaritmininei bazei 2 (bazė 3, bazė 4, bazė 5 ...) N įvesties dydis, o ne O (N).

Ir taip toliau.

54
21 февр. Atsakymas pateikiamas mėnulio šešėlis 21 vasaris. 2010-02-21 23:13 '10, 23:13, 2010-02-21 23:13

Geriausias būdas, kaip visada turėjau praktiškai vizualizuoti algoritmą, kuris veikia O (log n), yra toks:

Jei problemos dydį padidinsite daugybine verte (t.y., padauginkite jo dydį 10), darbas padidėja tik papildomai.

Taikydami šį klausimą savo dvejetainiam medžiui, kad turėtumėte gerą taikymą: jei dvigubai dvigubo medžio mazgų skaičius, aukštis padidinamas tik 1 (papildoma suma). Если вы удвоите его снова, он все равно только увеличится на 1. (Очевидно, я предполагаю, что он остается сбалансированным и таковым). Таким образом, вместо удвоения вашей работы, когда размер проблемы умножается, вы делаете только немного больше работы. Вот почему алгоритмы O (log n) являются удивительными.

48
ответ дан DivineWolfwood 22 февр. '10 в 22:51 2010-02-22 22:51

Какой журнал b (n)?