[Playlisten] [Impressum und Datenschutzerklärung]

12C.3 Zeitkomplexität; Beispiele für Groß-O-Notation

CC-BY-NC-SA 3.0

Nachtmodus Pausen an Schnitten Tempo: 0,5 0,7 1,0 1,3 1,5

Anklickbares Transkript:

noch mal zu der – Zeit Komplexität – wie lange läuft ein Programm – in Abhängigkeit – von der Menge an Daten die ich ihm gebe – ?? – Zeit Komplexität – so schön heißt – immer so mal das Suchen angucken das Suchen in einem – unsortierten – RE – dastehen von mir aus Zahlen drin wie üblich fängt an mit zweiundvierzig und dreizehn – hundert eins wie auch immer ich suche in diesem Rei eine Zahl – wenn dieses Rennen nicht sortiert – ist – ich hoffe das jetzt ?? oder drunter – und verzehrt – wenn dieses Rennen nicht sortiert ist habe ich keine andere Chance – als eins nach dem andern durchzugehen – der Hoffnung dass ich irgendwo meine Zahl findet ?? eben nicht finde – ist eine gegebene Zahl in einem gegebenen RE trennen oder nicht – müsste von vorne bis hinten durchsuchen wenn es nicht sortiertes wenn ich nicht über diese Reihe wüsste soll ich mal sagen wenn die Zahlen da drin stehen – wie sie halt den zufällig ohne dass ich was vorweist – wenn ich weiß vorne stehen kleinen Zahlen stehen die großen Zahlen ?? andere Geschichte wenn ich wüsste – vorn stehen die ungeraden Zahlen sind nicht in die geraden Zahlen – dann wäre das auch eine Geschichte aber wenn ich nichts über die Anordnung weist – listig – einen nach dem anderen vergleichen – und – das wäre von der Maximaldauer – her – wie lange – dauert – dieser – Algorithmus – wie lange läuft – dieser Algorithmus – wenn ich eins zwei – in Sachen habe – ich wirklich physikalisch vorstellen – der schlimmste Fall – sie haben in Sachen gegeben – was ist im schlimmsten – Fall die Laufzeit – könne im Prinzip tatsächlich ihr – ?? Kurve dann auf mal ich habe in Sachen gegeben wie lange wird es dauern soundsoviel Sekunden – keine Ahnung wenn sie zehn Sachen haben wird es soundsoviel Sekunden dauern maximal – wenn die zwei Sachen haben wird es soundsoviel Sekunden dauern das zu suchen – maximal – dreißig haben – jetzt sollte für dauern offensichtlich länger als mit zwanzig – das wären eher – Formeln die man erwarten würde für diese Sorte – in einem ?? von dem ich nichts weiß in dem Bereich den N Sachen drin – was würden Sie erraten wie diese maximale – Dauer der Suche abhängt von ähm – ?? müsste das Aussehen ✂ überlegen Sie ?? verwandeln die Maximaldauer – Eintritt die Maximaldauer – tritt ein wenn die Zahl die Suche der hinten drin steht oder gar nicht drinsteht – müssen nämlich alle angucken – wenn die erste Zahl schon die richtige ist oder sind sie fertig offener drei Milliarden Zahlen drin stehen – für die Maximaldauer – ist dann der Fall wenn die Zahl die ich suche da ganz hinten drin steht oder wenn sie gar nicht drin steht der sich alle angucken muss – so – und das noch mal im Hinterkopf behalten – sie zwei Sachen in der Liste haben – was passiert – wenn sie drei Sachen in der Liste haben mit der Zeit im Verhältnis zu – wenn die zwei Sachen in der Liste haben wie viel länger kann es dauern mit drei Sachen ✂ ?? habe mal so lang vom Gefühl her ich brauche soundsoviel Sekunden oder Millisekunden oder Nanosekunden – für einen – für eine Zelle – aus und solange dafür und dann nochmals und solange dafür das was ich brauch hier zweieinhalb – sozusagen Tier guck ich mir den ersten Antrag dazu und solange – den zweiten Anlauf noch mal solange ?? und den dritten andauert dreimal solange – also oben brauche ich zwei Zeiteinheiten – und brauche ich drei Zeiteinheiten – sollte also – aus dem Bauch heraus proportional – zu dieser Zahl – der Elemente in den Ray sein – was ich erwarten würde ist – manchmal so das unsere Pässe hier zu lesen ist – was sie erwarten würde ist eine Proportionalität – dass das hier eine gerade dadurch geht – eine Ursprungsgerade – das für dich erwarten proportional – zur Zahl der – Einträge in diesem Essay ist die Maximaldauer – wenn der N Sachen drin sind muss ich mir maximal abwegig in Sachen – angucken – also die Maximaldauer – der durch das ich was hinschreiben die Zeit – wird sein – irgend eine komische Proportionalitätskonstante – mal diese Zahl in – dieses habe dann sein – soundsoviel – Nanosekunden vielleicht – soundsoviel Nanosekunden – pro Eintrag – mal die Zahl der Einträge – über die Steigung der Narr – in – das wäre ganz einfache – ?? als Erfolgsmodell – für das was Mandatszeit – erwartet dass wir auf musealen System niemals so sein – wenn N in die Größenordnung von Millionen und Milliarden geht – Komma wenn ich denn Effekte rein – dass der Rechner – im Zugriff langsamer wird und so weiter aber das würde man erst mal – annehmen hat's als Zusammenhang dass das proportional zueinander ist – Komma würde obendrein noch was annehmen – man würde annehmen das es in grundsätzlichen – ?? am – ?? seines Sonne Grundlast – gibt es gibt sowieso einen gewissen Aufruf erstmals ohne Funktion aufzurufen – ?? egal ob ich sie für – eins oder eine Million Elemente aufrufe ?? es gibt grundsätzlichen Aufwand dafür – es heißt – die – Band würde – man würde ?? ausgehen dass die Kurve eher so aussieht – über noch der grundsätzliche Aufwand dabei sie noch ein Plus B sozusagen – das wäre – naja ein halbes realitätsgetreues – Modell für die – Zeit dies benötigt soundsoviel Sachen – zu durchsuchen – wie gesagt es dürfe nicht zu viele sein weil sonst – der Speicherzugriff langsamer wird und zum Schluss wenn sie nach einer keine Ahnung nach nach einem kann Regionen Sachen suchen – ?? sowieso gar nicht realistisch möglich ist aber im mathematischen – Modell – ist das – jetzt schreibt man – als – Zeitkomplexität – als Zeitkomplexität – schreibt man jetzt nicht diese konkrete Formel hin – was mich an der Zeitkontext – interessiert ist – wie es ist mehr oder minder – proportional – mit einem Versatz aber mehr oder minder proportional – und was dann der steht ist dieses Ding hier eine Konstante mal ähm – die – Zahl der Elemente die ich dem Algorithmus – gebe dem Verfahren gebe – ?? versandte mal endlos wem – das ist – Element – O von – N groß O von enden Sorten Personal geschrieben aus dieser Algorithmus – dieser einfache – Suchalgorithmus – der ist von der Zeit Komplexität – groß O – von N Ziel – googeln wollen sie unter Landau Symbole – das ist eines der Landau Symbole groß O von N – das kommt an dieser Stelle in der Informatik und auch in der Beschreibung von Algorithmen oder man sich anguckt wie die Standardbibliotheken – in – der ?? wird er dieses groß roh verwendet um zu sagen – okay das Wachstum – ihr – dieses Wachstum – ist von der Ordnung da wohl das groß O Herr für die meisten Leute ?? Interpretation – von der selben Ordnung wie – die reine Zahl N diese Konstante hier vor ?? möchte ich ignorieren – und das Plus B – resignierte ich auch noch gleich im Fluge – schreibe ?? ofenenden – mich interessiert nicht wie schnell das Iberia sehr schnell kurze Zeit und wie langsam es wirklich ist mich interessiert das Wachstum – das macht die Zeit – aus – wie schlimm ist dieser Algorithmus – der hier wäre mit ein hoch eins Hof von ?? noch eins – am – wenn ich ein zitiertes – RE habe dann kann ich raffinierter rangehen – vor Weihnachten – männlich einsortiert Reh habe – einen – dreizehnten – achtunddreißig – dreißig zweiundvierzig – fünfzig wie auch immer – kann ich raffinierter dran gehen und sagen – wenn ich jetzt zum Beispiel die Zahl fünfzehn Suche ist die Zahl fünfzehn drinnen – guck ich irgendwo in der Mitte fünfzig ist zu groß dann weiß ich ?? die – rechte Hälfte – plus minus einen gerechte Hälfte vergessen ich gucke noch in der linken Hälfte – ?? darf wieder in der Hälfte – oder plus minus eins der Hälfte sowie der nicht genau auf – dreißig ist so groß dann kann ich hier – den rechten Teil vergessen – dann kann ich mir die Beine noch angucken dreizehn ist zu klein fünfzehn ist gar nicht wenn – es diese fortlaufende Halbierung gewesen binäre Suche – und – bei binärer Suche was würden Sie da – als Maximaldauer – ansetzen – T ist gleich – was was würde ich da als Formel – hin schreiben wollen – irgendwas in Abhängigkeit von N was erwarte ich da als Formel – wenn ich ständig halbieren – wovon müsste die Zeit abhängen – kann ich das formulieren mit irgendwelchen Konstanten die man dann nicht kennt ✂ Probleme den Zusammenhang irgendwie zu skizzieren – logarithmisch – vermuten sie ja – so angenommen ich kriege – zehn Einträge – in dieser Zeit durchsucht – und man muss mit zwanzig passiert dreißig und mit vierzig – passiert – wie müssten die nächsten liegen – wie viel Zeit brauche ich für zwanzig Briefe Zeit brauche ich für vierzig – im Verhältnis dazu ✂ zwanzig ein Schritt mehr genau eine weitere Halbierung und für vierzig einen Schritt mehr – das heißt – für zwanzig nicht der Wert – einen Schritt weiter – gebrauchen ein Schritt mehr hier – das Intervall mehr und für vierzig – kriege ich zweimal ?? Intervall drauf – sicher – sogar noch weiter malen und das klarzumachen – für achtzig – Pfennig Treiber das Intervall drauf – ich brauche einen Schritt – um – bis zu vierzig zu kommen agieren und dann noch mal einen Schritt um bis zu zwanzig unter Nummer ein Schritt um bis zu zehn zu kommen sowie das aussehen – wenn sich das angucken – was das werden wird – das wird eine logarithmische Kurve werden – das ist der Witz da komplett logarithmische Kurve her wenn ich die Zahl ähm verdoppelte – brauche ich einen Schritt mehr – ein weiterer Halbierung ?? – in siehe sechzehn hätten wenn sie im ersten Schritt – auf acht kommen – investieren sollte finale Grund für den ersten Schritten hatte ?? noch acht – der Investitionsfinanzierung – für den zweiten Schritt und haben nur noch vier – letztes mörderisches Verhältnis – mit jeder Verdopplung von ?? ähm kommt – in der Drehachse hier ein weiterer Schritt dazu – das heißt ich würde als Formel – sowas vermuten wie – man mir stets – andere Rhythmus – bei der ?? der zwei lockere Busse sind das scheint erst nach zwei Rhythmus zu schreien weil ich fortlaufend halbieren – kommen aus ?? Block zwei statt LB und die – Lok zwei von N – mit irgendwelchen Konstanten – immer die Anwesenheit – sie und – die – Aktie noch – Konstante – Grundlast gibt sowas – dass die meines nach dem Logarithmus – das klarer machen so – die nach dem Rhythmus addieren – so konnte das Aussehen für dieses Verfahren – und – wenn Sie das vergleichen sehen Sie das ist natürlich ein viel langsameres Wachstum der Logarithmus – wächst viel langsamer – kriegt ja nur – Specs viel langsamer als N also das ist deshalb ein – besseres Verfahren das kann man an diesen Werten hier an diesen Formen auch ablesen eben hat mir etwas – wovon ähm – ?? und das hier ist in der Ordnung – von – Lok von ähm so würde man es dann aufschreiben – wovon noch von ?? – das wenn sie bei den Beschreibungen – der – Algorithmen – diese Suche in einem sortierten Array binäre Suchen am sortierten ?? – geht mit Lok von – im Endeffekt – was das bedeutet – dieses groß O – versus groß O bedeutet – zwischen zwei Funktion – an ich sage – eine Funktionselement – groß O – von einer anderen Funktion – wenn diese – erste Funktion – maximal – so schlimm wächst wie ein beliebig großes Vielfaches von der zweiten – also – das hier genau dann wenn – es gibt – eine Zahl – die sehr groß sein kann das gerne ähm es gibt eine Zahl im Management – er – mit der Eigenschaft – dass – diese – Funktion – links – schlimmstenfalls – wird – im Betrag – ähm mal die von Zuma typischerweise keine negativen Zahlenregister – keinen Ärger aber – sicherheitshalber – in die Funktion links schlimmstenfalls – ähm mal die Funktion rechts wird – für – alle ähm – oder alle in groß genug das möchte ich gern ich möchte das diese Funktion links – durch ein Vielfaches – ein festes Vielfaches der Funktion rechts – beschränkt werden kann – das heißt – groß O von N diese ?? diese Definition – die überlegt sich aber eigentlich niemand – ernsthaft – man – hat das zum Schluss im Gefühl dieses hier ist groß O – von Lok enden und dieses hier ist groß O – von N – und alle haben im Gefühl was sie damit meinen – wenn Sie – Sympathisanten – schreiben – das Komma jetzt mal damit sie auch was zu tun kriegen mal im – Detail an groß O – von Wurzel ähm groß O – von – Dan – groß O – von E hoch kennen – das offensichtlich richtig – langsam – wenn unser Algorithmus – so – wachsen kann in der Zeitdauer – für mehr Eingaben wenn sie – das – wenn Sie einen Link mehr eingeben braucht der Algorithmus – des Sohns vielfach an Zeit das ist schon heftig – wäre sowas – auch – Ange – was in der Praxis spannender ist natürlicher – Logarithmus von N – der DA Zehnerlogarithmus – LG der Zehnerlogarithmus – von ähm – geben Sie mal jeweils Funktionen an – Funktionen – die enthalten sind was wären Beispiele Funktionen enthalten sind – und – kann man sogar sagen – welche dieser Mengen welche andere enthält – welches – Ohr – enthält welches andere – erst – ein paar Beispiele zum Beispiel – Schweiz Komma dass man klarmachen – Komma mit dem hier O von N an – welche Funktion der zum Beispiel drin sind – wie es zum Beispiel einfach – per Maus schwierige – ganz billig wird hier drei – die Funktion die als Wert drei N ergibt – den – drei – N – im Verhältnis zu Ende – ist kein Problem – die Funktion von wegen drei N ist garantiert – immer kleiner gleich dreimal – als – ähm – was nicht ganz offensichtlich ist es auch drei N – Klos – tausend drin – weil – das ?? jedoch reinschreiben müssen – für alle in – die groß genug sind – ob sie das sie muss nicht sofort gelten das muss gelten wenn in groß genug ist – ?? nicht für N gleich eins gelten und in gleich zwei gelten – es muss ab irgendwann Geld informiert ?? endlich eine Million – sammel hiermit ein drei ähm plus tausend ?? über das dann hinein – tus tausend – drei in der Saison tausend sein bisschen – weit entfernt auf der y-Achse egal – dieses Ding – können wir mit der normalen – en vergleichen – nicht direkt leicht ab null ?? fängt einfach dein irgendwo an wenn sich hier von dem – ein Vielfaches nehmen an dem ihr – eine Ahnung das zehn tausend -fache nehmen – ist das überhaupt kein Problem – das uns vielfache der Kurve unten ähm – wird garantiert größer sein als das was sie aus dem drei endlos tausend aus Punkt – in diesem Sinne – denn sie sind noch ein paar weitere aus – was wären Beispiele für die – anderen hier was werden bei den anderen Funktionen die enthalten sind – und – gibt es welche von denen – die ganzen anderen drin sind ist keine Ahnung wovon – E hoch N in O von Entrinnen komplett – Fragezeichen – solche Geschichten ✂ ?? ja sicher oben – bei der Wurzel – ist zum Beispiel sowas drin wie zweiundvierzig – Mal die Wurzel von N – plus dreizehn – das würde funktioniert – und sie können noch dazu nehmen plus – eins durch ein zum Beispiel – inneres abstellt – als die Wurzelfunktion – bisher nach oben geschoben – ganz viel nach oben geschoben ?? lassen sie noch was abgefahrenes – dadrauf – addieren – dass es garantiert – alles in O von Wurzelenden – ich nehme die normale Wurzelfunktion – nach – ?? Funktion ich nehme die normale Wurzelfunktion – mal einen hinreichend großen Faktor – und sage – naja – gleich tausend oder sowas aufwärts – in dem es nötig ist wird es schon funktionieren dass es ja noch zittrig hier für alle Ende groß genug sind es muss nicht für ganz kleine en gelten – es muss – irgendwann gelten – weiter – eine Million – also eine Funktion – hier – die – ins unendliche hin – maximal – so schlimm wächst wie ein Vielfaches – von Wurzel in – maximal so schlimm wächst sie können auch Funktion haben – die viel langsamer wächst – sie können hier zum Beispiel auch drin haben – dann zweiundvierzig – plus – eins durch ein Quadratsgewächse – mich gar nicht die Feld – wenn sich eine ändert der Logarithmus – der wächst ja auch langsamer als die Wurzel zweiundvierzig – plus zum Beispiel – der – Zehnerlogarithmus – von N – würde auch gehen – Ehrung eines richtig fies der wächst superschnell – da hätten wir jedoch ähm – selber natürlich drin – aber nicht sowas wie Ehrung ein Quadrat zu entverlieren – und dann eh hoch das wäre noch Steller – das wäre was – sowas sozusagen – das wäre noch zu schnell das Gericht man auch im Wasser fifa nicht geregelt ✂ also genau sie dürfen hier – einen beliebig großen Faktor vorschreiben – tausendmal – jedoch ähm das würde funktionieren – das Problem ist – wenn man etwas hat – was – noch steigt stärker wächst als ich nach ein Vielfaches haben das Batzen groß Pro eingebaut ich darf ein Vielfaches haben ein konstantes – Vielfaches haben – aber dieses hier ein Quadrat ist der vom Type noch viel stärker wachsen ?? müsste man es immerhin mal – er mir mich sicher Vergleich mit dem jungen Quadrat kriege ich das hin das E hoch in Quadrat – kleiner gleich eine Konstante – mal die hoch N ist – für hinreichend große N – dass es aussichtslos – Entehrung – ein Quadrat wächst dermaßen stark – an ist es nicht hinkriegen kann ?? darüberliegende – könnte man das sogar begründen – das wären spannende Geschichte das Genuss sogar begründen – und dann – zeige – eh hoch ein Quadrat – das meines en Quadrat und dann eh hoch nehmen – junge Quadrat ist nicht in groß O – von E hoch N – am – ?? angenommen – mein Beweis dafür – angenommen – es ich hätte so eine Zahl Neo ein Quadrat – ist kleiner gleich irgend eine große Zahl – ähm mal die hoch ähm – ?? in großer gleich groß N – angenommen ?? das wäre der Fall wäre tatsächlich möglich dass sich ihr UN Quadrat deckte hierdurch ihre UN – dann – gründlicher umformen wie würden Sie das hier umformen – um was über ähm oder über en oder was auch immer rauszukriegen – wie könnte ich irgendwie zusammenfassen ✂ worin genau sie bringen ihr UN Römer – ein Quadrat – durch die hoch ähm ist kleiner gleich ähm für – und so weiter – ihre Quadrat durch die hoch ähm – was steht hier auf der linken Seite ✂ wird – man eher vorsichtig – an – die hoch – E hochla – durch die Hochclub – unsere Potenzen von E durch soundsoviel Potenzen von ihnen haben sie nachher soundsoviel Potenzen mi – ?? sowie Potenzen – das heißt sie haben hier eh hochenden – Quadrat minus N – das Patent – wurden in Quadratspotenzen – von E oben in zehn Separatpotenzen – und sind Senpotenzen – haben sie hier ein Quadrat minus N – Potenzen von insgesamt – das – soll – kleiner gleich ähm sein – für N groß genug was sie können sie sagen dass das nicht geht – wie so kann – es keine Zahl ähm geben – keine ideelle Zahl ähm geben die größer gleich Ehebruch in Quadrat minus N ist für alle in die groß genug sind Punkt dass sie ✂ genau das wird beliebig groß N vertrat minus ähm – die – Parabel minus N – die beiden voneinander abziehen was sie rauskriegen wird beliebig groß das Quadrat siegt über das ähm das hier wird unendlich werden – aber äh noch etwas das unendlich wird wird auch unendlich werden – sie bräuchten eine Zahl die größer gleich unendlich ist toll das wäre also keine reelle Zahl – das gar nicht funktioniert – jedoch ein Vertrag ist nicht – in O von ihr hoch in ihren Quadrat wächst stärker – die hoch ein – Komma kann es tatsächlich an einigen Stellen relativ einfach zeigen – wir mit dem Logarithmus – der ist natürlich der Engländerin – keine Frage – was halten Sie von dem Logarithmus – zur Basis – drei – ist der Logarithmus zur Basis drei – in of folgen L N – drin oder nicht ✂ Mathe ein schlankes ja dann – die Logarithmen sind alle zueinander proportional – wenn sind Logarithmus zur Basis drei haben wollen können Sie stattdessen auch den natürlichen – Rhythmus nehmen – und durch die natürlichen Rhythmus von drei Teilen – richte man beliebige Logarithmen – und warum sich jetzt – das auch der Dreierlogarithmus – in dieser Menge sein muss ✂ genau dass sie ständig das Wort eins durch LN von drei – NN – von N eine Constanze – Martin von N – das jetzt Constanze – dieselbe – Situation wie hier mit drei N und N oder je zwei vierzig Wurzel kurz – also – Doppelpunkt drei von N ist da drin – was müssen was wissen Sie dann sofort über – diese beiden letzten hier über den und den – was wissen Sie über die beiden ✂ die beiden sind dasselbe – bei – Kilo Rhythmen proportional zueinander sind – ist es egal ob sie Elaine von N schreiben oder ALG den Zehnerlogarithmus – von N schreiben diese beiden hier – sind dasselbe – dieselbe Menge und zum Schluss schreibt man dann eben einfach – wieder das eine hin noch das andere scheint aber locken und zu sagen ja wissen was wir meinen es ist egal – welcher Algorithmus – Hauptsache minder Basis über eins – ?? hier oben auch schon – war – er doch mit der ?? Block hingeschrieben so schreibt man es dann man gibt typischerweise nicht den Rhythmus an – sondern – verdienen so hat man irgendwelche – fiesen Kombinationen – hat der nicht der Rhythmus alleine steht – in malloc Rhythmus wird ?? noch funktioniert – in den fiesen Kombination vorkommt ?? Rhythmus dann könnte es wichtig werden anzugeben welche aber hier – ist es nicht wichtig welcher ?? – sie nehmen ein – Hauptsache seine Basis ist über eins zwo Meter – okay und andere Sachen sind noch in einen ineinander enthalten sehen Sie welche die ganz eindeutig ineinander enthalten sind – eine Menge die größer ist als eine andere Menge ✂ genau – der hier wächst am schlimmsten – war das Ismaning ?? – of von Ivo Enver wächst am schlimmsten von allen der enthält alle anderen – Handhelds zum Beispiel – O von – N – was ist derjenige der langsamsten – Wechselschwächen – schreibe ich ganz auf die linke Seite – genau ✂ der Logarithmus ist der langsamste von den widerstehen – habe ich hab es wirklich mal locker in – diesem Format Sinne nehmen irgendein Rhythmus Hauptsache die Basis über eins – und – Sommer noch – eine Wurzel endlich dann – dazwischen – Wurzel ist langsamer als ähm – lang anschaulich schon und das ist jetzt auf Malen muss – die Wurzelfunktion – haben und en haben – Richtungen endlich wird en viel stärker wachsen als die Wurzel aus N – das heißt – nebenbei auch noch wenn ich wenn ich wenn ich wenn ich hier Sohn Algorithmus – in die Zeitkapazität – eines Algorithmus – angebe als O von N – ich hätte hier auch schreiben können ist es Element von O von E hoch N – das wäre bisschen sehr sicher – und würde was nicht sagend sein wovon ich noch eine richtig langsame Funktionen sind – also – schnell wachsende Funktion langsamer Algorithmen sind – aber man hätte schreiben können es wäre mathematisch korrekt – und bei dem hier – Demir hätte ich auch schreiben können er ist in Hof von ähm – weiteren Rhythmus schneller ist – als das N – auch das schreiben können wäre nicht sehr – intelligent das so zu schreiben aber es wäre wahr – ?? müssen vorsichtig sein – wo man auch vorsichtig sein muss es ist eben das Asymptote Verhalten – an – was im unendlichen Schnelltest heißt nichts – wenn etwas im männlichen schneller ist im Vergleich heißt es nicht dass es im endlichen – schon schnell sein muss Sie können zum Beispiel – folgende Situation – haben – um – was man normal – einen Algorithmus – der so läuft – mit – irgendwas in Quadrat – Pluskonstante – alles was so ein Quadrat plus – dreizehn zu – sie können ein Algorithmus der so läuft haben – aber sie können – einen Algorithmus haben den der sich viel schneller anfühlt zumindest von der Formel her – sie können einen einen Algorithmus haben – von der Sorte mit dem Logarithmus – mal LG – von N – irgendwie verziert – dich hier – von vernünftige Sen aber langsamer – ist – als der wirklich das Handy muss die Kurve mit dem Logarithmus – liegen – das dich hier – über der schwarzen Kurve – kommt – denen ✂ sie können über seinen Sohn hervor wie auch dahinter setzen sie können sagen nehmen wir aber – tausend mal den Logarithmusglobus – tausend oder was – wir tausend mal den Rhythmus plus irgendwas dann klinge vielleicht sowas hin – im – unendlichen – hin – ist dieses Wachstum – viel kleiner als das Wachstum aber es kann mir passieren das ich für realistische – Größen – bei dem blauen Algorithmus langsamer bin als beim schwarzen – Gesandte – den deutschen Angaben mit of von Lok und mit of von N oder was auch immer dieser sind russischen Angaben gelten im unendlichen – ?? aber im wahren Leben mit endlichen Größen Zwischenzugang – ?? endlich groß Rays endlich große Datensätze wochenweise speichert und es kann sein dass wir endlich große Datensätze – das Verhältnis sich umkehrt – wird typischerweise – nicht passieren aber kann passieren – und man darf nicht zu viel Aufmerksamkeit – jetzt in dieser – of von soundsoviel – Angaben geben – diese die unendlichen – das wahre Leben ist nicht im ländlichen das wahre Leben ist im endlichen – und es kann sein – dass sie dann mit Funktion die of von soundsoviel mäßig besser aussehen – mit Algorithmen – die Opernsohn sowie mäßig besseres Aussehen in der Stadt bedarf – schlechter fahren – als mit Algorithmen die schlechter aussehen – vorsichtig sein – das es im – Groben – das mit den of von soundsoviel ?? ein solch noch – ganz in der Liste drin of von eins kommt ?? häufiger vor – of von eins – was heißt jetzt eigentlich of von eins ✂ was auf jeden Fall erlaubt es Berufen einzig eine konstante Zeit – als eine Vielfaches von eins ist das tausend fache von eins ist auch dann of von eins – die darf der Verlauf sonst noch sein – wenn eine Funktion O von eins sein soll ✂ zum Beispiel – abfallend würde auch funktionieren – so eine Funktion – den – ab – einem bestimmten ähm – ab einem bestimmten – enden soll ich – kleiner gleich ein Vielfaches von Einssein gar kein Problem – an diesem ähm sind sie kleiner gleich – diesem vielfachen von eins aus meiner abfallenden Funktion – auch kein Problem – überhaupt bei Funktionen die ins unendliche hin beschränkt bleiben und wenn sie irgendein Verlauf haben – Hauptsache zum Ende hin wird das Ding beschränkt bleiben und es dafür noch weiter schwanken – so – sowas – beschränkt das Chateau von eins für Sachen die beschränkt sind das dann – ein etwas – solch Versagen verwirrende Notation – meint man einfach – die Zeit es beschränkt egal viele Daten ich Reinstoffe – der Zeitaufwands beschränkt – das wäre zum Beispiel – an die Zeit – dies dauert – ein Element in einem Reh abzuspeichern – wenn sie dabei haben von Millionen – an Sachen wie lange dauert es eine Zahl darin abzuspeichern – dort genauso lange bei Millionen wie bei Milliarden – waren eben nicht ganz aber in der theoretischen Informatik ganz – das wäre dann auch von Einzel sind nicht von der Anzahl der Elemente ab wie lange es dauert eins abzuspeichern – an einer gegebenen Stelle