Ar yra atvejų, kai pageidaujate didesnio sudėtingo sudėtingumo algoritmo, palyginti su mažesniu?

Ar yra kokių nors atvejų, kai pageidaujate O(log n) laiko sudėtingumo O(1) laiko sudėtingumui? Arba O(n) į O(log n) ?

Ar turite kokių nors pavyzdžių?

236
09 дек. V.Leymarie 09 d. 2015-12-09 16:25 '15 - 16:25 2015-12-09 16:25
@ 22 atsakymai

Gali būti daug priežasčių, dėl kurių pageidaujate algoritmo, kurio sudėtingumas yra didesnis nei žemesnis:

  • Daugeliu atvejų sunkiau pasiekti mažesnį „O-O“ sudėtingumą, kuriam reikalingas kvalifikuotas įgyvendinimas, daug žinių ir daug testų.
  • big-O slepia detales apie konstantą: algoritmas, kuris veikia 10^5 yra geresnis iš big-O, nei 1/10^5 * log(n) ( O(1) ir O(log(n) ), požiūriu. bet labiausiai pagrįstai n pirmasis veiks geriau, pavyzdžiui, geriausias matricos dauginimo sudėtingumas yra O(n^2.373) bet konstanta yra tokia didelė, kad joks (kiek aš žinau) skaičiavimo bibliotekos nenaudoja.
  • big-o turi prasmę, kai tikitės kažką didelio. Jei jums reikia surūšiuoti trijų skaičių masyvą, tai nėra svarbu, jei naudojate O(n*log(n)) arba O(n^2) algoritmą.
  • kartais mažų atvejų sudėtingumo pranašumas gali būti nereikšmingas. Pavyzdžiui, yra tango medis, kurio duomenų struktūra suteikia O(log log N) laiko sudėtingumą ieškant elemento, tačiau yra ir dvejetainis medis, kuris suranda tą patį O(log n) . Netgi dideliems skaičiams n = 10^20 skirtumas yra nereikšmingas.
  • laiko sudėtingumas ne viskas. Įsivaizduokite algoritmą, kuris veikia O(n^2) ir reikalauja O(n^2) atminties. Tai gali būti geriau nei O(n^3) laikas ir O(1) erdvė, kai n nėra labai didelis. Problema yra ta, kad galite ilgai laukti, bet jūs labai abejojate, kad galite rasti pakankamai daug RAM, kad galėtumėte naudoti su savo algoritmu.
  • lygiagretinimas yra geras mūsų paskirstyto pasaulio bruožas. Yra algoritmų, kurie yra lengvai lyginami, tačiau yra algoritmų, kurie nėra lygiagrečiai. Kartais prasminga paleisti algoritmą 1000 įprastų mašinų, kurių sudėtingumas yra didesnis nei vienoje mašinoje su šiek tiek geresniu sudėtingumu.
  • kai kuriose vietose (saugumo) sudėtingumas gali būti reikalavimas. Niekas nenori turėti maišymo algoritmo, kuris gali išnykti žaibo greitai (nes tada kiti žmonės gali jus apgauti daug greičiau)
  • nors tai nėra susiję su sudėtingumo keitimu, kai kurios saugumo funkcijos turi būti parašytos taip, kad būtų užkirstas kelias laiko užpuolimui . Jie dažniausiai lieka toje pačioje sudėtingumo klasėje, tačiau yra modifikuojami taip, kad visada imtųsi blogiausio atvejo. Vienas pavyzdys lygina, kad stygos yra lygios. Daugumoje programų yra tikslinga greitai nutraukti, jei pirmieji baitai yra skirtingi, tačiau saugumu jūs vis tiek laukiate, kol baigsis galutinis pranešimas.
  • kažkas patentavo mažesnio sudėtingumo algoritmą, o ekonomiškiau įmonei naudoti didesnį sudėtingumą nei mokėti pinigus.
  • Kai kurie algoritmai gerai prisitaiko prie konkrečių situacijų. Pavyzdžiui, įterpimo rūšiavimas turi vidutinį laiko sudėtingumą O(n^2) , dar blogiau nei greitas rūšiavimas arba sujungimas, bet kaip veiklos algoritmas gali efektyviai rūšiuoti gautų vertybių sąrašą (kaip vartotojo įvestį), kur dauguma kitų Algoritmai gali veiksmingai veikti tik su pilnu vertybių sąrašu.
255
12 дек. Atsakymą pateikė Salvador Dali 12 d. 2015-12-12 11:03 '15, 11:03, 2015-12-12 11:03

Visada yra paslėpta konstanta, kuri gali būti mažesnė O (log n) algoritmu. Taigi praktikoje ji gali veikti greičiau, kad galėtų gauti realius duomenis.

Taip pat kyla problemų dėl erdvės (pavyzdžiui, dirbant su skrudintuvais).

Be to, kūrėjo laiko problema - O (log n) gali būti 1000 x lengviau įdiegti ir patikrinti.

227
09 дек. Atsakymas suteikiamas Alistra 09 d. 2015-12-09 16:27 '15 at 16:27 2015-12-09 16:27

Nustebau, kad niekas nepaminėjo su atmintimi susijusių programų.

Gali būti algoritmas, turintis mažiau slankiojo kablelio operacijų, arba dėl jo sudėtingumo (ty O (1) <O (log n)), arba dėl to, kad pastovumas prieš sudėtingumą yra mažesnis (ty 2 n 2 <6 n 2 ). Nepaisant to, jūs vis tiek galite rinktis algoritmą su dideliu FLOP kiekiu, jei žemesnis FLOP algoritmas labiau susijęs su atmintimi.

Ką aš turiu omenyje „atminties įpareigojimas“ yra tai, kad jūs dažnai gaunate prieigą prie duomenų, kurie yra nuolat už talpyklos. Jei norite išskirti šiuos duomenis, turite ištraukti atmintį iš savo tikrosios atminties vietos į savo talpyklą, kad galėtumėte ją atlikti. Šis mėginių ėmimo etapas dažnai yra gana lėtas - daug lėčiau nei jūsų operacija.

Todėl, jei jūsų algoritmas reikalauja daugiau operacijų (tačiau šios operacijos atliekamos su duomenimis, kurie jau yra talpykloje [ir todėl nereikia imtis mėginių], jis vis tiek atliks algoritmą su mažesniu operacijų skaičiumi (kuris turėtų būti atliekamas duomenimis) iš talpyklos [ir dėl to reikia imtis atrankos]) pagal faktinį sienos laiką.

57
09 дек. atsakymą pateikė „ NoseKnowsAll 09“. 2015-12-09 22:31 '15, 10:31 pm 2015-12-09 22:31

Tais atvejais, kai duomenų saugumas yra problema, sudėtingesnis algoritmas gali būti geriau nei mažiau sudėtingas algoritmas, jei sudėtingesnis algoritmas turi geresnį atsparumą sinchronizavimo metodams.

42
09 дек. Atsakymą pateikė Kevin K 09 dec. 2015-12-09 20:47 '15 ne 20:47 2015-12-09 20:47

Alistra jį prikalė, bet nepateikė jokių pavyzdžių, todėl aš.

Jūsų parduotuvėje yra 10 000 UPC kodų sąrašas. 10 skaitmenų UPC, sveikasis skaičius už kainą (kaina kapeikose) ir 30 simbolių.

Metodas

O (log N): turite surūšiuotą sąrašą. 44 baitai, jei ASCII, 84, jei Unicode. Arba, UPC laikykite kaip int64, ir gausite 42 ir 72 baitus. 10 000 įrašų - didžiausiu atveju esate šiek tiek mažesnis nei sandėliavimo megabaitas.

Metodas

O (1): nelaikykite UPC, vietoj to naudokite jį kaip raštą į masyvą. Mažiausiu atveju žiūrite beveik trečdalį atminties terabaito.

Kokį požiūrį naudojate, priklauso nuo jūsų įrangos. Bet kokioje pagrįstoje šiuolaikinėje konfigūracijoje naudosite log N metodą, galiu įsivaizduoti, kad antrasis požiūris yra teisingas atsakymas, jei dėl kokių nors priežasčių dirbate aplinkoje, kurioje RAM yra labai trumpas, bet jūs turite daug masinės atminties. Trečdalis disko terabaito nesvarbu, kad jūsų duomenys viename diske yra kažką vertingi. Paprastai paprastas dvejetainis požiūris trunka 13 metų. (Atkreipkite dėmesį, kad, klasterizuodami raktus, galite gauti jį prieš garantuotą 3 skaitymą, ir praktiškai jums bus talpyklos pirmasis.)

37
10 дек. Atsakymą pateikė Loren Pechtel . 2015-12-10 08:14 '15 at 8:14 2015-12-10 08:14

Apsvarstykite raudoną ir juodą medį. Ji turi prieigą, paiešką, įterpimą ir ištrinimą O(log n) . Palyginkite su masyvu, turinčiu prieigą prie O(1) , ir likusias operacijas - O(n) .

Taigi, taikomojoje programoje, į kurią mes įtraukiame, ištriname ar atliekame paiešką dažniau nei prieiga, ir pasirinkimas tarp šių dviejų struktūrų, mes norėtume raudoną juodą medį. Tokiu atveju galite pasakyti, kad pirmenybę teikiame raudonoms juodligėms virš sudėtingų O(log n) prieigos laikų.

Kodėl Kadangi prieiga nėra pagrindinė mūsų problema. Sudarome kompromisą: mūsų paraiškos veikimą didžia dalimi lemia ir kiti veiksniai. Mes leidžiame šiam konkrečiam algoritmui patirti našumą, nes optimizuojame kitus algoritmus.

Taigi atsakymas į jūsų klausimą yra toks: kai algoritmo augimo tempas nėra tas, kurį norime optimizuoti , kai norime optimizuoti kažką kito. Visi kiti atsakymai yra ypatingi šio atvejo atvejai. Kartais optimizuojame kitų operacijų vykdymo laiką. Kartais optimizuojame atmintį. Kartais optimizuojame saugumą. Kartais optimizuojame prieinamumą. Kartais optimizuojame kūrimo laiką. Netgi perkonfigūravimo konstanta, kuri yra pakankamai maža, kad išspręstų problemą, optimizuoja vykdymo laiką, kai žinote, kad algoritmo augimo tempas neturi didžiausią poveikį vykdymo laikui. (Jei jūsų duomenų rinkinys buvo už šio diapazono ribų, optimizuotumėte algoritmo augimo greitį, nes jis galiausiai dominuos pastovioje padėtyje.) Viskas turi kainą, o daugeliu atvejų mes prekiaujame didesniu augimo tempu, kad optimizuotume tai, kas kažkas kita.

35
10 дек. Atsakymą pateikė jpmc26 10 Dec. 2015-12-10 06:06 '15 - 06:06 2015-12-10 06:06

Taip

Tikruoju atveju atlikome kai kuriuos testus, atlikdami lentelės paiešką naudojant trumpus ir ilgus eilutės raktus.

Mes naudojome std::map , std::unordered_map su hash, kad pavyzdžiai ne daugiau kaip 10 kartų ilgio eilutės (mūsų raktai paprastai yra apytiksliai, todėl tai padorus) ir maišos, kad rodo kiekvieną simbolį (teoriškai sumažintas susidūrimų), nerūšiuoti vektorius, kuriame mes lyginame == , ir (jei teisingai prisimenu) nesirūšiuotą vektorių, kuriame mes taip pat saugome maišelį, pirmiausia lyginame maišelį ir tada lyginame simbolius.

Šie algoritmai svyruoja nuo O(1) (nereguliuojama) iki O(n) (tiesinė paieška).

Dėl nedidelio dydžio N, O (n) gana dažnai sugeba O (1). Mes įtariame, kad tai yra dėl to, kad konteineriai, pagrįsti mazgu, reikalavo, kad mūsų kompiuteris daugiau šokinėtų atmintyje, o konteineriai pagal valdovą nebuvo.

Tarp jų yra O(lg n) . Aš neprisimenu, kaip tai buvo.

Veiklos skirtumas buvo ne toks didelis, o dideliuose duomenų rinkiniuose hash rezultatas buvo geresnis. Taigi, mes įstrigo su neorganizuotu hash'o žemėlapiu.

Praktikoje, tinkamo dydžio n, O(lg n) yra O(1) . Jei jūsų kompiuteryje yra tik 4 milijardai įrašų, tada O(lg n) apribota virš 32 . (lg (2 ^ 32) = 32) (kompiuterių moksle, lg yra logaritminiam pagrindui 2).

Praktikoje lg (n) algoritmai yra lėtesni nei O (1) algoritmai ne dėl logaritminio augimo faktoriaus, bet todėl, kad lg (n) dalis paprastai reiškia, kad algoritmas turi tam tikrą sudėtingumo lygį, ir kad sudėtingumas suteikia didesnį pastovų koeficientą, nei bet koks „aukštis“, lygus lg (n).

Tačiau sudėtingi O (1) algoritmai (pavyzdžiui, maišos kartografavimas) gali lengvai turėti tą patį arba didesnį pastovų faktorių.

23
10 дек. atsakymą pateikė „ Yakk“ - Adam Nevraumont. 2015-12-10 19:21 '15, 19:21, 2015-12-10 19:21

Galimybė lygiagrečiai atlikti algoritmą.

Nežinau, ar egzistuoja O(log n) ir O(1) klasių pavyzdys, tačiau kai kurioms problemoms pasirinkti sudėtingesnę klasę turintis algoritmas, kai algoritmas yra lengviau vykdomas lygiagrečiai.

Kai kurie algoritmai negali būti lyginami, bet turi tokį mažo sudėtingumo klasę. Apsvarstykite kitą algoritmą, kuris pasieks tą patį rezultatą ir gali būti lengvai lyginamas, bet turi didesnę sudėtingumo klasę. Vykdant vieną mašiną, antrasis algoritmas yra lėtesnis, bet kai atliekamas keliuose įrenginiuose, faktinis vykdymo laikas tampa mažesnis ir mažesnis, o pirmasis algoritmas negali būti pagreitintas.

21
10 дек. Atsakymas pateikiamas Simulantas 10 gruodis. 2015-12-10 12:37 '15, 12:37 2015-12-10 12:37

Tarkime, įterpti juodąjį sąrašą įterptinėje sistemoje, kur galima įrašyti 0–1 000 000 numerių. Tai palieka dvi parinktis:

  • Naudokite bitų rinkinį, turintį 1 000 000 bitų
  • Naudokite suskirstytą sveikųjų skaičių masyvą su juodu sąrašu ir naudokite dvejetainę paiešką, kad galėtumėte juos pasiekti.

Prieiga prie beta versijos bus garantuota nuolatinė prieiga. Laiko sudėtingumo požiūriu tai yra optimali. Tiek teorinis, tiek praktinis taškų vaizdas (tai yra O (1), turintis labai mažą patvarią viršutinę dalį).

Tačiau galite pasirinkti antrąjį sprendimą. Ypač jei tikitės, kad sveikųjų skaičių juodųjų sąrašų skaičius būtų labai mažas, nes jis bus veiksmingesnis atminties požiūriu.

Ir net jei nesukūrėte įdėtos sistemos, kurioje nėra pakankamai atminties, savavališką limitą galiu padidinti nuo 1 000 000 iki 1 000 000 000 000 ir padaryti tą patį argumentą. Tada bitų rinkiniui reikės apie 125 GB atminties. Netinkamo O (1) sudėtingumo užtikrinimas negali įtikinti jūsų viršininko, kad suteiktų jums tokį galingą serverį.

Čia aš norėčiau binarinę paiešką (O (log n)) arba dvejetainį medį (O (log n)) rinkinyje O (1). Ir, tikriausiai, maišos lentelė su blogiausiu sudėtingumu O (n) praktiškai juos nugalės.

15
11 дек. Atsakymą pateikė Philipp Claßen 11 d. 2015-12-11 03:29 '15 at 3:29 2015-12-11 03:29

Mano atsakymas čia yra greitas atsitiktinis svertinis pasirinkimas visose stochastinės matricos eilutėse yra pavyzdys, kai algoritmas su sudėtingumu O (m) yra greitesnis nei vienas su sudėtingumu O (log (m)), kai m nėra per didelis.

13
10 дек. Atsakymą pateikė Warren Weckesser 10 dec. 2015-12-10 01:49 '15 at 1:49 2015-12-10 01:49

Žmonės jau atsakė į jūsų konkretų klausimą, todėl pasiskirsčiau šiek tiek kitokį klausimą, kurį žmonės gali galvoti, kai jie ateina čia.

Daugelis "O (1) laiko" algoritmų iš tikrųjų naudoja tik tikėtinus O (1) kartus, o tai reiškia, kad jų vidutinis veikimo laikas yra O (1), galbūt tik tam tikromis prielaidomis.

Bendrieji pavyzdžiai: „ hashtables“, „masyvų sąrašų“ išplėtimas (matricos / vektoriai su dinamišku dydžiu).

Tokiuose scenarijuose galite naudoti duomenų struktūras arba algoritmus, kurių laikas garantuojamas absoliučiai ribotas logaritmu, net jei jie gali būti vidutiniškai blogesni.
Todėl pavyzdys yra subalansuotas dvejetainis paieškos medis, kurio veikimo laikas yra vidutiniškai blogesnis, bet blogiau.

12
12 дек. Atsakymą pateikė Mehrdad, gruodžio 12 d. 2015-12-12 01:54 '15 at 1:54 2015-12-12 01:54

Bendresnis klausimas yra tai, kad yra situacijų, kai algoritmas O(f(n)) turėtų naudoti O(g(n)) algoritmą O(g(n)) , nors g(n) << f(n) kaip n linkęs į begalybę. Kaip sakė kiti, atsakymas yra aiškiai „taip“, kai f(n) = log(n) ir g(n) = 1 . Kartais taip, net jei f(n) yra polinomas, bet g(n) yra eksponentinis. Gerai žinomas ir svarbus pavyzdys yra paprastojo algoritmo metodas linijinių programavimo problemų sprendimui. Aštuntajame dešimtmetyje buvo įrodyta, kad O(2^n) . Todėl jo blogiausias elgesys neįmanomas. Tačiau - jo elgesys vidutiniškai yra labai geras, net ir dėl praktinių problemų, turinčių dešimtys tūkstančių kintamųjų ir suvaržymų. Devintajame dešimtmetyje linijiniam programavimui buvo atrasta polinomo laiko algoritmai (pvz., Carmarkara interjero taško algoritmas ), tačiau po 30 metų simpleksinis algoritmas vis dar reprezentuojamas pasirinkimo algoritmu (išskyrus keletą labai didelių problemų). Taip yra dėl akivaizdžios priežasties, kad elgesys vidutiniu atveju dažnai yra svarbesnis už blogiausio atvejo elgesį, bet ir dėl subtilesnės priežasties, kad simpleksinis algoritmas tam tikra prasme yra informatyvesnis (pavyzdžiui, jautrumo informacija yra lengviau išskiriama).

11
11 дек. John Coleman atsakymas 11 d 2015-12-11 00:24 '15 prie 0:24 2015-12-11 00:24

Įdėkite 2 centus į:

Kartais vietoj geriausio algoritmo pasirenkamas blogiausias sudėtingumo algoritmas, kai algoritmas veikia konkrečioje aparatūros aplinkoje. Tarkime, kad mūsų O (1) algoritmas nuosekliai nenurodo kiekvieno labai didelio fiksuoto dydžio masyvo elemento mūsų problemai išspręsti. Tada įdėkite šį masyvą į mechaninį standųjį diską arba magnetinę juostą.

Šiuo atveju O (logn) algoritmas (manydamas, kad jis pasiekia diską nuosekliai) tampa palankesnis.

10
12 дек. Atsakymas pateiktas Reek 12 d. 2015-12-12 15:25 '15 15:25 2015-12-12 15:25

Paprasta: kadangi veiksnys - išlaidos, susijusios su šio veiksmo nustatymu, saugojimu ir trukme, gali būti daug didesnės nei mažesnė problema su didesniu O nei didesniame. Big-O yra tik algoritmų mastelio matavimo priemonė.

Apsvarstykite šį pavyzdį iš įsilaužėlių žodyno, siūlančio rūšiavimo algoritmą, pagrįstą kvantinės mechanikos kelių pasaulių aiškinimu :

  • Perduokite masyvą atsitiktinai naudojant kvantinį procesą
  • Jei masyvas nėra surūšiuotas, sunaikinkite visatą.
  • Dabar visos kitos visatos yra rūšiuojamos [įskaitant ir tuos, kuriuos esate].

(Šaltinis: http://catb.org/~esr/jargon/html/B/bogo-sort.html )

Atkreipkite dėmesį, kad šio algoritmo didelis O yra O(n) , kuris yra didesnis už bet kokį žinomą rūšiavimo algoritmą bendrų elementų dieną. Linijinis žingsnio koeficientas taip pat yra labai mažas (kadangi tai tik palyginimas, o ne apsikeitimas, kuris atliekamas tiesiškai). Toks algoritmas galėtų būti naudojamas bet kokiai problemai spręsti tiek NP, tiek bendroje NP srityje polinominiu laiku, nes kiekvienas galimas sprendimas (arba galimas įrodymas, kad nėra tirpalo) gali būti generuojamas naudojant kvantinį procesą ir išbandytas polinominiu laiku.

Tačiau daugeliu atvejų tikriausiai nenorime rizikuoti tuo, kad keli pasauliai gali būti neteisingi, jau nekalbant apie tai, kad antrojo veiksmo veiksmas vis dar lieka „skaitytojo pratimas“.

9
13 дек. „Hansinator“ atsakymas yra gruodžio 13 d 2015-12-13 07:12 '15, 7:12 2015-12-13 07:12

Yra geras pasirinkimas naudoti O (log (n)) algoritmą vietoj O (1) algoritmo, kurį ignoruoja daugybė kitų atsakymų: nekintamumas. Kryžminiuose žemėlapiuose O (1) užima ir gauna, darant prielaidą, kad skydo vertės yra gerai paskirstytos, tačiau joms reikalinga nepastovi būsena. Keičiantys medžio žemėlapiai turi O (log (n)), o tai yra asimptotiškai lėtesnė. Однако неизменность может быть достаточно ценной, чтобы компенсировать худшую производительность, и в случае, когда необходимо сохранить несколько версий карты, неизменность позволяет избежать копирования карты, которая является O (n), и, следовательно, может улучшить производительность.

9
ответ дан Solomonoff's Secret 11 дек. '15 в 22:07 2015-12-11 22:07

В любой точке, когда n ограничено, а константный множитель алгоритма O (1) выше, чем оценка на log (n). Например, сохранение значений в хэш-наборе равно O (1), но может потребовать дорогостоящего вычисления хэш-функции. Если элементы данных могут быть тривиально сопоставлены (по отношению к некоторому порядку), а оценка по n такова, что log n значительно меньше, чем вычисление хэша на любом одном элементе, то сохранение в сбалансированном двоичном дереве может быть быстрее, чем сохранение в hashset.

7
ответ дан Dmitry Rubanovich 13 дек. '15 в 0:05 2015-12-13 00:05