Ar yra kokių nors O (1 / n) algoritmų?

Ar yra kokių nors O (1 / n) algoritmų?

Arba kas nors mažesnė nei O (1)?

319
25 мая '09 в 9:15 2009-05-25 09:15 Shalmanese nustatė gegužės 25 d., 09:15, 2009-05-25 09:15
@ 34 atsakymai
  • 1
  • 2

Šis klausimas nėra toks kvailas, kaip atrodo. Bent jau teoriškai kažkas panašaus į O (1 / n) yra visiškai pagrįsta, kai matuojame matmenį Big O :

2019

296
25 мая '09 в 11:10 2009-05-25 11:10 atsakė Konradui Rudolphui gegužės 25 d., 09:10, 2009-05-25 11:10

Taip

Yra lygiai vienas algoritmas su vykdymo laiku O (1 / n), „tuščiu“ algoritmu.

Algoritmui O (1 / n) reiškia, kad jis atlieka asimptotiškai mažiau žingsnių nei algoritmas, kurį sudaro viena komanda. Jei jis įvykdomas mažiau nei vienu žingsniu visiems n> n0, tai turi sudaryti tiksliai jokios instrukcijos n. Kadangi patikrinimas „jei n> n0“ yra bent 1 komanda, jis neturėtų turėti jokių nurodymų visiems n.

Apibendrinimas: vienintelis algoritmas, kuris yra O (1 / n), yra tuščias algoritmas, kurį sudaro ne instrukcijos.

126
11 июня '09 в 20:40 2009-06-11 20:40 atsakymas buvo duotas Tobiasui birželio 11 d., 09:40, 2009-06-11 20:40

Tai neįmanoma. Big-O apibrėžimas neviršija nelygybės:

 A(n) = O(B(n)) <=> exists constants C and n0, C > 0, n0 > 0 such that for all n > n0, A(n) <= C * B(n) 

Taigi, B (n) iš tikrųjų yra didžiausia reikšmė, todėl, jei jis mažėja didėjant n, sąmatos nesikeis.

25
25 мая '09 в 9:21 2009-05-25 09:21 atsakymą pateikė aštrus gegužės 25 d., 09:21, 2009-05-25 09:21

aštrus, teisingas, O (1) yra geriausias rezultatas. Tačiau tai nereiškia greito sprendimo, tik nustatyto laiko.

Įdomi galimybė ir galbūt tai, ką iš tikrųjų siūloma, yra problemos, kurios tampa vis lengvesnės, nes didėja gyventojų skaičius. Aš galiu galvoti apie 1, nors aš išrado insolenciją:

Ar du žmonės rinkinyje turi vieną gimtadienį? Kai n viršija 365, grįžkite tiesa. Nors mažiau nei 365 yra O (n ln n). Galbūt tai nėra puikus atsakymas, nes problema lėtai nesudaro paprastesnė, bet tiesiog tampa O (1), kai n> 365.

23
25 мая '09 в 10:01 2009-05-25 10:01 atsakymą pateikė Adrianas gegužės 25 d., 09:01, 2009-05-25 10:01

Iš ankstesnio didelės O žymos tyrimo, net jei jums reikia 1 žingsnio (pvz., Kintamojo tikrinimas, užduoties atlikimas), tai yra O (1).

Atkreipkite dėmesį, kad O (1) sutampa su O (6), nes "pastovus" neturi reikšmės. Todėl sakome, kad O (n) sutampa su O (3n).

Taigi, jei jums reikia tik vieno žingsnio, tada O (1) ... ir kadangi jūsų programai reikia bent 1 žingsnio, minimalus algoritmas gali eiti, tai yra O (1). Jei, jei ne, tai manau, tai yra O (0)? Jei darome viską, tai yra O (1), ir bent jau ji gali eiti.

(Jei nuspręstume to nedaryti, tai gali tapti Zen arba Tao problema ... programavimo srityje O (1) vis dar yra minimalus).

Arba kaip tai padaryti:

programuotojas : bosas, aš rasiu būdą tai padaryti O (1) kartus!
bosas : nereikia to padaryti, šiandien bankrutavome.
programuotojas : oh, tada jis tampa O (0).

15
25 мая '09 в 9:47 2009-05-25 09:47 atsakymas duotas 生 者 無極 而 生 Gegužės 25 d., 09:47, 2009-05-25 09:47

Ne, tai neįmanoma:

Kadangi n linkęs į begalybę 1 / n, mes galiausiai pasiekiame 1 / (inf), o tai yra 0.

Taigi didelė problemos klasė bus O (0), turinti didžiulį n, bet arčiau laiko konstantos su žemu n. Tai yra nepagrįsta, nes vienintelis dalykas, kurį galima padaryti greičiau nei pastovus laikas, yra:

void nothing() {};

Ir netgi tai įmanoma!

Kai tik įvykdysite komandą, turite bent O (1), todėl ne, mes negalime turėti O klasės (1 / n)!

8
25 мая '09 в 15:45 2009-05-25 15:45 atsakymą pateikė Ed James , gegužės 25 d., 05:45, 2009-05-25 15:45

Aš dažnai vartoju O (1 / n), kad apibūdintume tikimybes, kurios mažėja, kai padidėja įvesties duomenys - pavyzdžiui, tikimybė, kad log2 (n) bus rodoma teisinga moneta yra O (1 / n).

7
25 мая '09 в 20:52 2009-05-25 20:52 atsakymas duotas Dave gegužės 25 d., 09:52, 2009-05-25 20:52

Kaip apie neveikia funkcija (NOOP)? arba naudojant fiksuotą vertę. Ar tai skaičiuojama?

7
25 мая '09 в 11:10 2009-05-25 11:10 atsakymą pateikė SpliFF gegužės 25 d., 09:10, 2009-05-25 11:10

O (1) paprasčiausiai reiškia „pastovus laikas“.

Pridėjus ankstyvą išėjimą į kilpą [1], jūs (įraše su dideliu O) pasukite O (1) į O (n), bet tai darysite greičiau.

Apskritai dėmesys yra geriausias algoritmas su pastoviu laiku, o linijinis yra geriau eksponentinis, tačiau mažais kiekiais n eksponentinis algoritmas gali būti greitesnis.

1: Darant prielaidą šio pavyzdžio statinio sąrašo ilgį

6
25 мая '09 в 15:28 2009-05-25 15:28 atsakymas pateikiamas LapTop006 gegužės 25 d., 09:28, 2009-05-25 15:28

Tiems, kurie skaito šį klausimą ir nori suprasti, kas pasakyta, tai gali padėti:

 | |constant |logarithmic |linear| N-log-N |quadratic| cubic | exponential | | n | O(1) | O(log n) | O(n) |O(n log n)| O(n^2) | O(n^3) | O(2^n) | | 1 | 1 | 1 | 1| 1| 1| 1 | 2 | | 2 | 1 | 1 | 2| 2| 4| 8 | 4 | | 4 | 1 | 2 | 4| 8| 16| 64 | 16 | | 8 | 1 | 3 | 8| 24| 64| 512 | 256 | | 16 | 1 | 4 | 16| 64| 256| 4,096 | 65536 | | 32 | 1 | 5 | 32| 160| 1,024| 32,768 | 4,294,967,296 | | 64 | 1 | 6 | 64| 384| 4,069| 262,144 | 1.8 x 10^19 | 
5
30 апр. Craig O'Connor atsakymas, pateiktas balandžio 30 d 2016-04-30 04:57 '16 at 4:57 2016-04-30 04:57

Manau, kad kvantiniai algoritmai gali atlikti kelis skaičiavimus „iš karto“ per superpoziciją ...

Aš abejoju, kad tai naudingas atsakymas.

5
25 мая '09 в 9:20 2009-05-25 09:20 Atsakymą davė Jeff Meatball Yang gegužės 25 d., 09:20, 2009-05-25 09:20

daugelis žmonių turėjo teisingą atsakymą (Ne). Čia yra dar vienas būdas jį įrodyti: norint turėti funkciją, turite skambinti funkcijai, ir jums reikia grąžinti atsakymą. Tai užima tam tikrą pastovų laiką. O jeigu likusioji apdorojimo trukmė trunka mažiau laiko dideliems įėjimams, spausdinant atsakymą (kurį mes galime laikyti vienu bitu) užtrunka mažiausiai pastovus laikas.

3
09 июля '10 в 22:29 2010-07-09 22:29 atsakė Brian Postow'ui liepos 10 d. 10 val. 10:29 2010-07-09 22:29

Jei sprendimas yra, jis gali būti paruoštas ir prieinamas pastoviu laiku = nedelsiant. Pavyzdžiui, naudojant LIFO duomenų struktūrą, jei žinote, kad rūšiavimo užklausa vykdoma atvirkštine tvarka. Tada duomenys jau surūšiuoti, jei pasirinktas tinkamas modelis (LIFO).

2
25 мая '09 в 9:32 2009-05-25 09:32 atsakymą pateikė „ Larsson “ gegužės 25 d., 09:32, 2009-05-25 09:32

Funkcijų ir jų pavedimų sąrašas yra O () , kurį pateikia Viki teta.

2
25 мая '09 в 9:31 2009-05-25 09:31 atsakymą pateikė devio gegužės 09 d., 09:31 2009-05-25 09:31

Jūs negalite eiti žemiau O (1), tačiau galimas O (k), kur k yra mažesnis nei N. Mes juos pavadinome sublinear laiko algoritmais . Kai kuriose problemose, sublinear laiko algoritmas gali pateikti tik apytikslius konkrečios problemos sprendimus. Tačiau kartais apytiksliai sprendimai yra puikūs, tikriausiai todėl, kad duomenų rinkinys yra per didelis, arba todėl, kad viską apskaičiuoti yra pernelyg brangu.

2
25 мая '09 в 9:51 2009-05-25 09:51 atsakymą pateikė Hao Wooi Lim , gegužės 25 d., 09:51, 2009-05-25 09:51

Kokios problemos tampa lengvesnės, kai gyventojų skaičius auga? Vienas atsakymas yra dalykas, pvz., Bittorrent, kur atsisiuntimo greitis yra atvirkštinė mazgų skaičiaus funkcija. Skirtingai nuo automobilio, kuris sulėtėja, tuo daugiau įkelsite, failų pasidalijimo tinklas, pvz., Bittorrent, pagreitina daugiau mazgų.

2
25 мая '09 в 10:22 2009-05-25 10:22 atsakymą pateikė Niklas Rosencrantz gegužės 09 d. 10:22 2009-05-25 10:22

O (1 / n) yra ne mažesnis kaip O (1), tai iš esmės reiškia, kad kuo daugiau duomenų, tuo greičiau algoritmas veikia. Tarkime, jūs gaunate masyvą ir visada užpildysite jį iki 10 elementų 100, jei jis turi mažiau, ir nieko nedaro, jei jų yra daugiau. Žinoma, tai nėra O (1 / n), bet kažkas panašaus į O (-n) :) Per blogai O-didžiojo pavadinimo neleidžia neigiamų verčių.

1
25 мая '09 в 9:32 2009-05-25 09:32 atsakymą pateikė vava gegužės 25 d., 09:32, 2009-05-25 09:32

Kaip jau minėta, be galimo nulinės funkcijos išskyrimo, O(1/n) funkcijos negali būti, nes šiuo atveju laikas artėja prie 0.

Žinoma, yra keletas panašių į Conrad apibrėžtų algoritmų, kurie, matyt, turėtų būti mažesni nei O(1) bent jau tam tikra prasme.

 def get_faster(list): how_long = 1/len(list) sleep(how_long) 

Jei norite ištirti šiuos algoritmus, turite apibrėžti savo asimptotinį matmenį arba savo laiko sampratą. Pavyzdžiui, aukščiau pateiktame algoritme galėčiau leisti, kad keli „laisvi“ veiksmai būtų naudojami tam tikrą skaičių kartų. Pirmiau pateiktame algoritme, jei aš apibrėžiau t ', išskyrus laiką visam, išskyrus miego, tada t' = 1 / n, kuris yra O (1 / n). Tikriausiai yra geresnių pavyzdžių, nes asimptotinis elgesys yra nereikšmingas. Tiesą sakant, esu įsitikinęs, kad kažkas gali sugalvoti jausmus, kurie duoda netradicinius rezultatus.

1
09 июля '10 в 14:19 2010-07-09 14:19 Atsakymą pateikė Casebash liepos 10 d., 10 val. 14:19 2010-07-09 14:19

Dauguma kitų atsakymų interpretuoja big-O tik algoritmo trukmei. Bet kadangi šis klausimas nebuvo paminėtas, aš maniau, kad verta paminėti kitą didelio skaičiaus O skaičiaus analizę, kuri yra susijusi su klaida.

Daugelis algoritmų gali būti O (h ^ p) arba O (n ^ {- p}), priklausomai nuo to, ar kalbate apie žingsnio dydį (h), ar padalinių skaičių (n). Pavyzdžiui, Euler metode ieškote y (h) sąmatos, atsižvelgiant į tai, kad žinote y (0) ir dy / dx (gautas iš y). Jūsų sąmata y (h) yra tikslesnė, arčiau h yra 0. Taigi tam, kad rastumėte y (x) tam tikrą savavališką x, užtrunka intervalas nuo 0 iki x, sulaužomas iki n dalių ir prasideda Euler metodas kiekviename taške, gaunamas iš y ( 0) iki y (x / n) iki y (2x / n) ir tt

Taigi Eulerio metodas yra O (h) arba O (1 / n), kur h paprastai interpretuojamas kaip žingsnio dydis, o n aiškinamas kaip kartų intervalas.

Taip pat galite naudoti O (1 / h) realaus pasaulio skaitinės analizės taikomosiose programose dėl slankiojo kablelio apvalinimo klaidų . Kuo mažesnis jūsų intervalas, tuo daugiau panaikinamas tam tikrų algoritmų įgyvendinimas, dideli reikšmingų skaičių praradimai ir todėl daugiau klaidų, kurios yra perduodamos per algoritmą.

Jei naudojate „Euler“ metodą, jei naudojate plūduriuojančius taškus, naudokite pakankamai nedidelį žingsnį ir atšaukite, o prie didelio skaičiaus pridėsite nedidelį skaičių, paliekant nemažą skaičių. Algoritmams, kurie apskaičiuoja išvestį, iš dviejų įvertintų funkcijų atėmus du skaičius labai artimose pozicijose, apytiksliai y '(x) su (y (x + h) - y (x) / h) lygiomis funkcijomis y (x + h ) artėja prie y (x), kuris lemia didelį išvestinių finansinių priemonių atšaukimą ir vertinimą su mažesniu reikšmingų skaitmenų skaičiumi. Tai, savo ruožtu, taikoma bet kuriam algoritmui, kuriam reikia išvestinės priemonės (pvz., Ribinių verčių problema).

1
30 июля '17 в 5:07 2017-07-30 05:07 atsakymą pateikė Andrew Lei, liepos 30 d. 17, 17:07 2017-07-30 05:07

Manau, kad mažiau nei O (1) neįmanoma. Bet koks laikas, kurį imasi algoritmas, vadinamas O (1). Bet O (1 / n), kaip apie šią funkciją. (Žinau, kad šiame sprendime jau yra daug variantų, bet manau, kad jie visi turi tam tikrų trūkumų (o ne pagrindinius, jie gerai paaiškina koncepciją).

 def 1_by_n(n, C = 10): #n could be float. C could be any positive number if n <= 0.0: #If input is actually 0, infinite loop. while True: sleep(1) #or pass return #This line is not needed and is unreachable delta = 0.0001 itr = delta while delta < C/n: itr += delta 

Taigi, didinant n, funkcija užtruks mažiau ir mažiau laiko. Taip pat garantuojama, kad jei įvestis yra 0, funkcija bus grąžinta visam laikui.

Galima teigti, kad tai bus apribota mašinos tikslumu. taigi, sinc eit turi viršutinę ribą, tai yra O (1). Bet mes taip pat galime tai apeiti n ir C reikšmes į eilutę. Ir papildymas ir palyginimas atliekamas linijoje. Idėja yra ta, kad šiuo atveju mes galime sumažinti n, kiek pageidaujama. Taigi, viršutinė funkcijos riba nėra ribojama, net jei ignoruojame n = 0.

Taip pat manau, kad negalime tiesiog pasakyti, kad vykdymo laikas yra O (1 / n). Bet mes turime pasakyti kažką panašaus į O (1 + 1 / n)

0
27 янв. atsakymas, kurį pateikė user1953366 Jan 27 2019-01-27 04:21 '19 at 4:21 AM 2019-01-27 04:21

Aš matau algoritmą, lygų O (1 / n), tačiau viršutinė riba:

Turite didelę įvesties seriją, kuri keičiasi dėl kažko išorinio subroutino (jie gali atspindėti aparatūrą, arba netgi gali būti kitas procesorius, kuris jį vykdo). bet galioja.

Dabar, jei ji nepasikeitė, tiesiog sukurkite elementų sąrašą, pasirinkite vieną atsitiktinai ir gaukite laiką O (1). Tačiau dinamiškas duomenų pobūdis pašalina sąrašo sudarymą, tiesiog reikia atsitiktinai išbandyti ir patikrinti zondo tikslumą. (Ir atkreipkite dėmesį, kad iš esmės nėra jokios garantijos, kad atsakymas išliks galiojantis, kai jis sugrįš. Jis vis dar gali būti naudojamas - tarkim, žaidimo vieneto AI. Jis gali nušauti tikslą, kuris nukrito iš akių, kai ji buvo traukiantis trigerį.)

Jis turi blogiausią begalybės našumą, tačiau vidutinis taikomųjų programų našumas mažėja, kai užpildo duomenų erdvę.

0
28 мая '09 в 3:36 2009-05-28 03:36 atsakė Loren Pechtel gegužės 28 d., 09:36 2009-05-28 03:36

Kaip apie tai:

 void FindRandomInList(list l) { while(1) { int rand = Random.next(); if (l.contains(rand)) return; } } 

augant sąrašui, numatomas programos vykdymo laikas mažėja.

0
25 мая '09 в 9:37 2009-05-25 09:37 atsakymą pateikė Shalmanese , gegužės 25 d., 09:37, 2009-05-25 09:37

Skaitmeninėje analizėje aproksimacijos algoritmai turėtų turėti subkonstantą asimptotinį komplekso suderinamumo toleranciją.

 class Function { public double[] ApproximateSolution(double tolerance) { // if this isn't sub-constant on the parameter, it rather useless } } 
0
24 янв. atsakymą pateikė Sam Harwell 24 d 2010-01-24 03:12 '10, 3:12, 2010-01-24 03:12

Gerai, aš šiek tiek apie tai galvojau, ir galbūt yra toks algoritmas, kuris galėtų sekti šią bendrąją formą:

Turite apskaičiuoti kelionės mazgo problemą 1000 mazgų, bet taip pat pateikiamas svetainių, kurių negalite aplankyti, sąrašas. Kadangi nematomų mazgų sąrašas didėja, problema tampa lengviau išspręsta.

0
25 мая '09 в 9:32 2009-05-25 09:32 atsakymą pateikė Shalmanese , gegužės 25 d., 09:32, 2009-05-25 09:32

2007 m. Turėjau tokią abejonę, malonu matyti šią temą, atėjau į šią temą iš mano reddit gijos → http://www.reddit.com/r/programming/comments/d4i8t/trying_to_find_an_algorithm_with_its_complexity/

-1
24 авг. atsakymas pateikiamas hemanth.hm 24 rug . 2010-08-24 17:09 '10, 17:09, 2010-08-24 17:09

Nežinau apie algoritmus, bet atsitiktinių imčių algoritmuose yra mažesnis nei O (1) sudėtingumas. Iš tiesų, o (1) (mažai o) yra mažesnė nei O (1). Toks sudėtingumas paprastai atsiranda atsitiktinių imčių algoritmuose. Pavyzdžiui, kaip minėjote, kai įvykio tikimybė yra 1 / n, jie nurodo jį naudojant o (1). Arba, kai jie nori pasakyti, kad kažkas vyksta didelės tikimybės (pavyzdžiui, 1 - 1 / n), tai reiškia 1 - o (1).

-1
24 апр. Atsakyti A. Mashreghi 24 bal . 2016-04-24 22:15 '16 at 10:15 pm 2016-04-24 22:15

Galima sukurti algoritmą, kuris yra O (1 / n). Vienas iš pavyzdžių galėtų būti ciklas, kuris kartoja keletą f (n) -n kartų kartotinių, kur f (n) yra tam tikra funkcija, kurios vertė garantuojama didesnė nei n, o riba f (n) -n, kai n artėja prie begalybės nulio. F (n) skaičiavimas taip pat turėtų būti pastovus visiems n. Aš nežinau, kas atrodo f (n), arba kokia programa turėtų tokį algoritmą, tačiau, mano nuomone, tokia funkcija gali egzistuoti, tačiau gautas algoritmas neturėtų jokio kito tikslo, tik įrodyti galimybę naudoti algoritmą su O (1 / n).

-1
30 апр. atsakymas, kurį pateikė Greg 30 Bal 2011-04-30 02:08 '11 at 2:08 2011-04-30 02:08

Čia yra paprastas O (1 / n) algoritmas. Ir tai netgi daro kažką įdomaus!

 function foo(list input) { int m; double output; m = (1/ input.size) * max_value; output = 0; for (int i = 0; i < m; i++) output+= random(0,1); return output; } 

O (1 / n) yra įmanoma, nes jame aprašoma, kaip funkcijos išėjimas keičiasi, kai padidėja įvesties dydis. Jei naudojame 1 / n funkciją, norėdami apibūdinti funkcijų atliktų komandų skaičių, nėra reikalavimo, kad ši funkcija priimtų bet kokio įvesties dydžio nulinius nurodymus. Labiausiai tikėtina, kad kiekvienam įvesties dydžiui n, viršijančiam tam tikrą slenkstį, reikalingų instrukcijų skaičius viršijamas teigiama konstanta, padauginta iš 1 / n. Kadangi nėra faktinio skaičiaus, kuriam 1 / n yra 0, ir konstanta yra teigiama, tada nėra jokios priežasties, kodėl ši funkcija apsiribotų 0 ar mažiau instrukcijų.

-2
16 сент. atsakymas, kurį pateikė ejspencer rugsėjo 16 d 2009-09-16 01:43 '09 ne 1:43 2009-09-16 01:43

Jei atsakymas yra vienodas, nepriklausomai nuo įvesties, turite O (0) algoritmą.

kitaip tariant - atsakymas žinomas prieš pateikiant įvesties duomenis - funkcija gali būti optimizuota, kad O (0)

-2
25 мая '09 в 11:15 2009-05-25 11:15 atsakymas pateikiamas pro gegužės 25 d., 09:15, 2009-05-25 11:15

Nieko mažiau nei O (1) „Big-O“ rašymas reiškia didžiausią algoritmo sudėtingumo tvarką

Jei algoritmas turi vykdymo laiką n ^ 3 + n ^ 2 + n + 5, tada tai O (n ^ 3) Žemutinės jėgos nesvarbu, nes kai n → Inf, n ^ 2 bus nesvarbi, palyginti su n ^ 3

Panašiai, kai n → Inf, O (1 / n) yra nesvarbus, palyginti su O (1), todėl 3 + O (1 / n) bus tokie patys kaip O (1), todėl O (1) yra mažiausias skaičiavimo sudėtingumas

-2
28 мая '09 в 3:08 2009-05-28 03:08 atsakymą pateikė vartotojo112831 gegužės 28 d. 09:08 2009-05-28 03:08
  • 1
  • 2