mogelijk Duplicaat:
Wat is het verschil tussen θ (n) en o (n)?
Het lijkt mij als wanneer mensen het overalgorithm complexiteit informeel praten, praten ze over Big-Oh. Maar in formele situaties zie ik vaak Big-Theta met de occasionele Big-Oh gegooid.
Ik ken wiskundig wat het verschil is tussen de twee, maar in het Engels, in welke situatie zou Big-Oh gebruiken als je bedoelt dat Big-Theta onjuist wees of vice versa (een voorbeeld algoritme zou worden gewaardeerd)?
Bonus: Waarom gebruiken mensen altijd BIG-OH bij het informeel praten?
1, Autoriteit 100%
BIG-O is een bovengrens.
Big-Theta is een strakke gebonden, d.w.z. bovenste en ondergrens.
Wanneer mensen zich alleen zorgen maken over wat het ergste is dat kan gebeuren, is BIG-O voldoende; d.w.z. er staat dat “het niet veel slechter kan worden dan dit”. Het strakker de gebonden, natuurlijk, maar een strakke gebonden is niet altijd gemakkelijk te berekenen.
Zie ook
Gerelateerde vragen
De volgende offerte uit Wikipedia werpt ook wat licht:
Informeel, vooral in de informatica, is de grote O-notatie vaak
toegestaan om enigszins misbruikt te zijn om een asymptotische strakke gebonden te beschrijven
waar het gebruik van de Big Theta-notatie kan worden opgericht in a
gegeven context.Bijvoorbeeld bij het overwegen van een functie
T(n) = 73n3+ 22n2+ 58, al het volgende zijn in het algemeen aanvaardbaar, maar de dichtheid van gebonden (dwz kogels 2 en 3 hieronder) hebben meestal sterk de voorkeur boven laxness van gebonden (dwz bullet 1
hieronder).
T(n) = O(n100), die identiek is aanT(n) ∈ O(n100)T(n) = O(n3), die identiek is aanT(n) ∈ O(n3)T(n) = Θ(n3), die identiek is aanT(n) ∈ Θ(n3)De equivalente Engelse uitspraken zijn respectievelijk:
T(n)groeit asymptotisch niet sneller dann100T(n)groeit asymptotisch niet sneller dann3T(n)groeit asymptotisch zo snel alsn3 .Dus terwijl alle drie de uitspraken waar zijn, is geleidelijk meer informatie in
elk. In sommige gebieden is de grote O-notatie (kogels nummer 2 in de bovenstaande lijsten)
zou vaker worden gebruikt dan de grote theta-notatie (kogels nummer 3 in de
Lijsten hierboven) omdat functies die langzamer groeien, wenselijker zijn.
2, Autoriteit 46%
Ik ben een wiskundige en ik heb big-O O(n), big-Theta Θ(n)en big-Omega Ω(n)notatie keer op keer, en niet alleen voor de complexiteit van algoritmen. Zoals mensen zeiden, is big-Theta een tweezijdige binding. Strikt genomen zou je het moeten gebruiken als je wilt uitleggen dat dat is hoe goed een algoritme kan doen, en dat ofwel dat algoritme niet beter kan of dat geen enkel algoritme het beter kan doen. Als je bijvoorbeeld zegt “Sorteren vereist Θ(n(log n)) vergelijkingen voor invoer in het slechtste geval”, dan leg je uit dat er een sorteeralgoritme is dat O(n(log n)) vergelijkingen gebruikt voor elke invoer ; en dat er voor elk sorteeralgoritme een invoer is die het dwingt om Ω(n(log n)) vergelijkingen te maken.
Een beperkte reden waarom mensen O gebruiken in plaats van Ω is om disclaimers over de slechtste of gemiddelde gevallen te laten vallen. Als u zegt “sorteren vereist O(n(log n)) vergelijkingen”, dan geldt de uitspraak nog steeds voor gunstige invoer. Een andere beperkte reden is dat zelfs als het ene algoritme om X te doen tijd kost Θ(f(n)), een ander algoritme het misschien beter doet, dus je kunt alleen maar zeggen dat de complexiteit van X zelf O(f(n)) is.
Er is echter een bredere reden waarom mensen O informeel gebruiken. Op menselijk niveau is het vervelend om altijd tweezijdige uitspraken te doen als de keerzijde “duidelijk” is uit de context. Aangezien ik een wiskundige ben, zou ik idealiter altijd voorzichtig zijn om te zeggen: “Ik neem een paraplu als en alleen als het regent” of “Ik kan met 4 ballen jongleren, maar niet met 5”, in plaats van “Ik neem een paraplu als het regent”. regens” of “Ik kan met 4 ballen jongleren”. Maar de andere helften van dergelijke uitspraken zijn vaak duidelijk bedoeld of duidelijk niet bedoeld. Het is gewoon de menselijke natuur om slordig te zijn over de voor de hand liggende. Het is verwarrend om haren te splitsen.
Helaas is het in een rigoureus gebied, zoals wiskunde of theorie van algoritmen, ook verwarrend om geen haren te splitsen. Mensen zullen onvermijdelijk O zeggen terwijl ze Ω of hadden moeten zeggen. Details overslaan omdat ze “duidelijk” zijn, leidt altijd tot misverstanden. Daar is geen oplossing voor.
Antwoord 3, autoriteit 19%
Omdat mijn toetsenbord een O-toets heeft.
Het heeft geen Θ- of Ω-toets.
Ik vermoed dat de meeste mensen even lui zijn en O gebruiken als ze Θ bedoelen, omdat het makkelijker is om te typen.
Antwoord 4, autoriteit 7%
Een reden waarom de grote O zo veel wordt gebruikt, is dat hij zo vaak wordt gebruikt. Veel mensen zien de notatie en denkendat ze weten wat het betekent, en gebruiken het dan zelf (verkeerd). Dit gebeurt veel met programmeurs wiens formele opleiding maar zo ver ging – ik was ooit zelf schuldig.
Een andere reden is dat het op de meeste niet-Griekse toetsenborden gemakkelijker is om een grote O te typen dan een grote theta.
Maar ik denk dat veel komt door een soort paranoia. Ik heb een tijdje in defensiegerelateerd programmeren gewerkt (en wist destijds heel weinig van algoritmeanalyse). In dat scenario zijn de prestaties in het slechtste geval altijd waar mensen in geïnteresseerd zijn, omdat dat slechtste geval zich op het verkeerde moment kan voordoen. Het maakt niet uit of de daadwerkelijke kans dat dat gebeurt b.v. veel minder dan de kans dat alle leden van een scheepsbemanning op hetzelfde moment een plotselinge hartaanval krijgen – het kannog steeds gebeuren.
Hoewel veel algoritmen natuurlijk hun slechtste geval hebben in veel voorkomende omstandigheden – het klassieke voorbeeld is het invoegen in volgorde in een binaire boom om te krijgen wat in feite een enkelvoudig gekoppelde lijst is. Een “echte” beoordeling van gemiddelde prestaties moet rekening houden met de relatieve frequentie van verschillende soorten input.
Antwoord 5, autoriteit 6%
Bonus: Waarom gebruiken mensen altijd BIG-OH bij het informeel praten?
Omdat in BIG-OH, deze lus:
for i = 1 to n do
something in O(1) that doesn't change n and i and isn't a jump
is O(n), O(n^2), O(n^3), O(n^1423424). Big-Oh is slechts een bovengrens, wat het gemakkelijker maakt om te berekenen omdat u geen strakke gebonden hoeft te vinden.
De bovenstaande loop is alleen big-theta(n)echter.
Wat is de complexiteit van de zeef van eratosthenes ? Als u zei O(n log n)zou u niet verkeerd zijn, maar het zou ook niet het beste antwoord zijn. Als u zei big-theta(n log n), zou u het mis hebben.
6
Er zijn hier veel goede antwoorden, maar ik merkte dat er iets ontbrak. De meeste antwoorden lijken te impliceren dat de reden waarom mensen grote O over Big Theta gebruiken, een moeilijkheidsgraad, en in sommige gevallen kan dit waar zijn. Vaak is een bewijs dat leidt tot een groot theta-resultaat is veel meer betrokken dan een die resulteert in grote O. Dit houdt meestal waar, maar ik geloof niet dat dit een grote relatie heeft met het gebruik van één analyse over de andere.
Als we praten over complexiteit kunnen we veel dingen zeggen. Grote O-tijdcomplexiteit vertelt ons gewoon wat een algoritme is gegarandeerd om binnen te rennen, een bovengrens. Grote Omega is veel minder vaak besproken en vertelt ons de minimumtijd die een algoritme is gegarandeerd om te rennen, een ondergrens. Nu vertelt Grote Theta ons dat beide nummers in feite hetzelfde zijn voor een bepaalde analyse. Dit vertelt ons dat de aanvraag een zeer strikte looptijd heeft, die alleen kan afwijken door een waarde die asymptief minder is dan onze complexiteit. Veel algoritmen hebben eenvoudigweg geen boven- en ondergrens die toevallig asymptief equivalent zijn.
Dus wat betreft uw vraag met behulp van grote O in plaats van grote Theta zou technisch altijd geldig zijn, terwijl het gebruik van grote theta in plaats van grote O alleen geldig zou zijn wanneer Big O en Grote Omega is toevallig gelijk. Bijvoorbeeld Insertion Sort heeft een tijdcomplexiteit van Big ® op N ^ 2, maar het beste casescenario legt zijn grote omega bij n. In dit geval zou het niet correct zijn om te zeggen dat de tijdcomplexiteit van zijn tijd groot is van N of N ^ 2, omdat ze twee verschillende grenzen zijn en als zodanig moeten worden behandeld.
7
Ik heb grote theta gezien en ik ben er vrij zeker van dat ik het verschil op school heb geleerd. Ik moest het echter opzoeken. Dit is wat Wikipedia zegt:
Big O is de meest gebruikte asymptotische notatie voor het vergelijken van functies, hoewel in veel gevallen BIG O kan worden vervangen door grote theta θ voor asymptotisch strakkere grenzen.
Bron: big o notatie # gerelateerde asymptotische notatie
Ik weet niet waarom mensen Big-O gebruiken als ze formeel praten. Misschien is het omdat de meeste mensen meer bekend zijn met Big-O dan met Big-Theta? Ik was vergeten dat Big-Theta zelfs bestond, totdat je me eraan herinnerde. Hoewel mijn geheugen nu is opgefrist, kan ik het uiteindelijk in een gesprek gebruiken. 🙂