{"id":12410,"date":"2020-05-28T09:00:00","date_gmt":"2020-05-28T07:00:00","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=12410"},"modified":"2025-06-12T09:11:56","modified_gmt":"2025-06-12T07:11:56","slug":"o-notation-zeitkomplexitaet","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/o-notation-zeitkomplexitaet\/","title":{"rendered":"O-Notation und Zeitkomplexit\u00e4t \u2013 anschaulich erkl\u00e4rt"},"content":{"rendered":"\n<p>Die O-Notation (ausgesprochen: \"Gro\u00df O Notation\")\u00b9 wird eingesetzt, um die Komplexit\u00e4t von Algorithmen zu beschreiben.<\/p>\n\n\n\n<p>Auf Google und YouTube findet man zahlreiche Artikel und Videos, die die O-Notation erkl\u00e4ren. Doch f\u00fcr das Verst\u00e4ndnis der meisten davon (wie z. B. dieses <a rel=\"noopener\" href=\"https:\/\/de.wikipedia.org\/wiki\/Landau-Symbole\" target=\"_blank\">Wikipedia-Artikels<\/a>), sollte man als Vorbereitung ein Mathematik-Studium absolviert haben. ;-)<\/p>\n\n\n\n<p>In diesem Artikel werde ich daher die O-Notation und die damit beschriebene Zeit- und Platzkomplexit\u00e4t ausschlie\u00dflich anhand von Beispielen und Diagrammen erkl\u00e4ren \u2013 und ganz ohne mathematische Formeln, Beweisf\u00fchrungen und Symbole wie \u03b8, \u03a9, \u03c9, \u2208, \u2200, \u2203 und \u03b5.<\/p>\n\n\n\n<p>Alle Quellcodes aus diesem Artikel findest du in diesem <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\" target=\"_blank\">GitHub-Repository<\/a>.<\/p>\n\n\n\n<p class=\"hc-footnote has-very-light-gray-background-color has-background\">\u00b9 alternative Bezeichnungen: \"Landau-Notation\" oder \"Asymptotische Notation\"; englisch: \"Big O notation\".<\/p>\n\n\n\n\n\n<h2 class=\"wp-block-heading\" id=\"arten-von-komplexitat\">Arten von Komplexit\u00e4t<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"zeitkomplexitat\">Zeitkomplexit\u00e4t<\/h3>\n\n\n\n<p>Zeitkomplexit\u00e4t (englisch: \"computational time complexity\") beschreibt die \u00c4nderung der Ausf\u00fchrungszeit eines Algorithmus in Abh\u00e4ngigkeit von der \u00c4nderung der Gr\u00f6\u00dfe der Eingabedaten.<\/p>\n\n\n\n<p>Oder anders gesagt: \"Um wie viel verlangsamt sich ein Algorithmus, wenn die Menge der Eingabedaten gr\u00f6\u00dfer wird?\"<\/p>\n\n\n\n<p>Beispiele:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Wie viel l\u00e4nger dauert es ein Element innerhalb eines <em>unsortierten<\/em> Arrays zu suchen, wenn sich die Gr\u00f6\u00dfe des Arrays verdoppelt? (Antwort: doppelt so lange)<\/li>\n\n\n\n<li>Wie viel l\u00e4nger dauert es ein Element innerhalb eines <em>sortierten <\/em>Arrays zu suchen, wenn sich die Gr\u00f6\u00dfe des Arrays verdoppelt? (Antwort: einen Schritt mehr)<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"platzkomplexitat\">Platzkomplexit\u00e4t<\/h3>\n\n\n\n<p>Platzkomplexit\u00e4t (englisch: \"space complexity\") beschreibt, wie viel zus\u00e4tzlichen Speicherplatz ein Algorithmus in Abh\u00e4ngigkeit von der Gr\u00f6\u00dfe der Eingabedaten ben\u00f6tigt.<\/p>\n\n\n\n<p>Damit ist <em>nicht<\/em> der Speicherbedarf f\u00fcr die Eingabedaten selbst gemeint (d. h. dass man f\u00fcr ein doppelt so gro\u00dfes Eingabe-Array selbstverst\u00e4ndlich doppelt so viel Platz ben\u00f6tigt), sondern derjenige Speicher, den der Algorithmus f\u00fcr Schleifen- und Hilfsvariablen, tempor\u00e4re Datenstrukturen und Call Stack (z. B. durch Rekursion) zus\u00e4tzlich ben\u00f6tigt.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"komplexitatsklassen\">Komplexit\u00e4tsklassen<\/h2>\n\n\n\n<p>Algorithmen werden in sogenannte Komplexit\u00e4tsklassen eingeteilt. Eine Komplexit\u00e4tsklasse wird mit dem Landau-Symbol <em>O<\/em> (\"Gro\u00df O\") gekennzeichnet.<\/p>\n\n\n\n<p>Im folgenden stelle ich die wichtigsten Komplexit\u00e4tsklassen vor, wobei ich mit den leicht verst\u00e4ndlichen Klassen beginne und dann zu den etwas komplizierteren komme. Dementsprechend sind die Klassen nicht nach Aufwand sortiert.<\/p>\n\n\n<div class=\"convertkit-form wp-block-convertkit-form\" style=\"\"><script async data-uid=\"5c918c0177\" src=\"https:\/\/happycoders.kit.com\/5c918c0177\/index.js\" data-jetpack-boost=\"ignore\" data-no-defer=\"1\" data-no-optimize=\"1\" nowprocket><\/script><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"o-1-konstanter-aufwand\">O(1) \u2013 konstanter Aufwand<\/h3>\n\n\n\n<p>Ausgesprochen: \"O von 1\"<\/p>\n\n\n\n<p>Die Ausf\u00fchrungszeit ist konstant, also unabh\u00e4ngig von der Anzahl der Eingabeelemente <em>n<\/em>.<\/p>\n\n\n\n<p>Im folgenden Graph stellt die horizontale Achse die Anzahl der Eingabeelemente <em>n<\/em> (oder allgemeiner: die Gr\u00f6\u00dfe des Eingabeproblems) dar und die vertikale Achse die ben\u00f6tigte Zeit.<\/p>\n\n\n\n<p>Da Komplexit\u00e4tsklassen nur verwendet werden k\u00f6nnen, um Algorithmen <em>einzuordnen<\/em>, nicht aber, um deren <em>genaue Laufzeit<\/em> zu berechnen, sind die Achsen nicht beschriftet.<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"412\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-o1-konstanter-aufwand-800x412.png\" alt=\"Komplexit\u00e4tsklasse O(1) \u2013 konstanter Aufwand\" class=\"wp-image-12508\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-o1-konstanter-aufwand-800x412.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-o1-konstanter-aufwand-224x115.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-o1-konstanter-aufwand-336x173.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-o1-konstanter-aufwand-504x259.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-o1-konstanter-aufwand-672x346.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-o1-konstanter-aufwand-400x206.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-o1-konstanter-aufwand-600x309.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-o1-konstanter-aufwand-944x486.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-o1-konstanter-aufwand-1200x617.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-o1-konstanter-aufwand.png 1520w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Komplexit\u00e4tsklasse O(1) \u2013 konstanter Aufwand<\/figcaption><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\" id=\"o-1-beispiele\">O(1) Beispiele<\/h4>\n\n\n\n<p>Die folgenden zwei Problemstellungen sind Beispiele f\u00fcr konstanten Aufwand:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Zugriff auf ein bestimmtes Element eines Arrays der Gr\u00f6\u00dfe <em>n<\/em>: Egal wie gro\u00df ein Array ist, der Zugriff \u00fcber <code>array[index]<\/code> ben\u00f6tigt immer die gleiche Zeit\u00b2.<\/li>\n\n\n\n<li>Einf\u00fcgen eines Elements am Anfang einer verketteten Liste: Dies erfordert immer das Setzen von einem bzw. zwei (bei einer doppelt verketteten Liste) Zeigern (oder Referenzen), unabh\u00e4ngig davon, wie gro\u00df die verkettete Liste ist. (Bei einem Array hingegen m\u00fcssten dazu alle Werte um ein Feld nach rechts verschoben werden, was bei einem gr\u00f6\u00dferen Array l\u00e4nger dauert als bei einem kleineren.)<\/li>\n<\/ul>\n\n\n\n<p class=\"hc-footnote has-very-light-gray-background-color has-background\">\u00b2 Hundertprozentig korrekt ist diese Aussage nicht, denn hier kommen auch noch Effekte durch die CPU-Caches ins Spiel: Wenn der Datenblock, der das auszulesende Element enth\u00e4lt, bereits (oder noch) im CPU-Cache liegt (wof\u00fcr die Wahrscheinlichkeit gr\u00f6\u00dfer ist, je kleiner das Array ist), dann ist der Zugriff schneller, als wenn dieser erst aus dem RAM gelesen werden muss.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"o-1-beispiel-quellcode\">O(1) Beispiel-Quellcode<\/h4>\n\n\n\n<p>Der folgende Quellcode (Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/simple\/ConstantTimeSimpleDemo.java\" target=\"_blank\">ConstantTimeSimpleDemo<\/a> im GitHub-Repository) zeigt ein einfaches Beispiel zur Messung des Aufwandes f\u00fcr das Einf\u00fcgen eines Elements am Anfang einer verketteten Liste:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">main<\/span><span class=\"hljs-params\">(String&#091;] args)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> n = <span class=\"hljs-number\">32<\/span>; n &lt;= <span class=\"hljs-number\">8_388_608<\/span>; n *= <span class=\"hljs-number\">2<\/span>) {\n    LinkedList&lt;Integer&gt; list = createLinkedListOfSize(n);\n\n    <span class=\"hljs-keyword\">long<\/span> time = System.nanoTime();\n    list.add(<span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">1<\/span>);\n    time = System.nanoTime() - time;\n\n    System.out.printf(<span class=\"hljs-string\">\"n = %d -&gt; time = %d ns%n\"<\/span>, n, time);\n  }\n}\n\n<span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> LinkedList&lt;Integer&gt; <span class=\"hljs-title\">createLinkedListOfSize<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> n)<\/span> <\/span>{\n  LinkedList&lt;Integer&gt; list = <span class=\"hljs-keyword\">new<\/span> LinkedList&lt;&gt;();\n  <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; n; i++) {\n    list.add(i);\n  }\n  <span class=\"hljs-keyword\">return<\/span> list;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Bei mir liegen die ben\u00f6tigten Zeiten \u2013 ungleichm\u00e4\u00dfig \u00fcber die verschiedenen Messungen verteilt \u2013 zwischen 1.200 ns und 19.000 ns. F\u00fcr einen schnellen Test reicht das aus. Allerdings bekommen wir hier keine besonders guten Messergebnisse, da sowohl HotSpot-Compiler als auch Garbage Collector jederzeit anspringen k\u00f6nnen.<\/p>\n\n\n\n<p>Bessere Messergebnisse liefert das Testprogramm <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/TimeComplexityDemo.java\" target=\"_blank\">TimeComplexityDemo<\/a> mit der Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/problem\/ConstantTime.java\" target=\"_blank\">ConstantTime<\/a>. Hier werden zun\u00e4chst mehrere Warmup-Runden ausgef\u00fchrt, um dem HotSpot-Compiler die Gelegenheit zu geben den Code zu optimieren. Erst danach werden wiederholt Messungen vorgenommen und der Median der Messwerte ausgegeben.<\/p>\n\n\n\n<p>Hier ein Auszug der Ergebnisse:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"Klartext\" data-shcb-language-slug=\"plaintext\"><span><code class=\"hljs language-plaintext\">--- ConstantTime (results 5 of 5) ---\nConstantTime, n =        32 -&gt; fastest: 31,700 ns, median: 44,900 ns\nConstantTime, n =    16,384 -&gt; fastest: 14,400 ns, median: 40,200 ns\nConstantTime, n = 8,388,608 -&gt; fastest: 34,000 ns, median: 51,100 ns<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Klartext<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">plaintext<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Der Aufwand bleibt also in etwa gleich, unabh\u00e4ngig von der Gr\u00f6\u00dfe der Liste. Die vollst\u00e4ndigen Testergebnisse findest du in der Datei <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/test-results.txt\" target=\"_blank\">test-results.txt<\/a>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"o-n-linearer-aufwand\">O(n) \u2013 linearer Aufwand<\/h3>\n\n\n\n<p>Ausgesprochen: \"O von n\"<\/p>\n\n\n\n<p>Der Aufwand w\u00e4chst linear mit der Anzahl der Eingabeelemente <em>n<\/em>: Verdoppelt sich <em>n<\/em>, dann verdoppelt sich auch ungef\u00e4hr der Aufwand.<\/p>\n\n\n\n<p>\"Ungef\u00e4hr\" deshalb, weil der Aufwand auch Komponenten mit niedrigeren Komplexit\u00e4tsklassen enthalten kann. Diese fallen bei hinreichend gro\u00dfem <em>n<\/em> nicht ins Gewicht, so dass sie bei der Notation vernachl\u00e4ssigt werden.<\/p>\n\n\n\n<p>In folgendem Diagramm habe ich das dadurch demonstriert, dass der Graph etwas oberhalb des Nullpunkts beginnt (der Aufwand enth\u00e4lt also auch eine konstante Komponente):<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"412\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-linearer-aufwand-v3-800x412.png\" alt=\"Komplexit\u00e4tsklasse O(n) \u2013 linearer Aufwand\" class=\"wp-image-12566\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-linearer-aufwand-v3-800x412.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-linearer-aufwand-v3-224x115.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-linearer-aufwand-v3-336x173.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-linearer-aufwand-v3-504x259.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-linearer-aufwand-v3-672x346.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-linearer-aufwand-v3-400x206.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-linearer-aufwand-v3-600x309.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-linearer-aufwand-v3-944x486.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-linearer-aufwand-v3-1200x617.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-linearer-aufwand-v3.png 1520w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\" id=\"o-n-beispiele\">O(n) Beispiele<\/h4>\n\n\n\n<p>Die folgenden Problemstellungen sind Beispiele f\u00fcr linearen Aufwand:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Finden eines bestimmten Elements in einem Array: Es m\u00fcssen dazu alle Elemente des Arrays betrachtet werden \u2013 bei doppelt so vielen Elementen dauert es doppelt so lang.<\/li>\n\n\n\n<li>Summieren aller Elemente eines Arrays: Auch daf\u00fcr m\u00fcssen alle Elemente einmal betrachtet werden \u2013 ist das Array doppelt so gro\u00df, dauert es doppelt so lang.<\/li>\n<\/ul>\n\n\n\n<p>Es ist wichtig zu verstehen, dass die Komplexit\u00e4tsklasse keine Aussage \u00fcber die absolut ben\u00f6tigte Zeit macht, sondern lediglich \u00fcber die \u00c4nderung der ben\u00f6tigten Zeit in Abh\u00e4ngigkeit von der \u00c4nderung der Eingabegr\u00f6\u00dfe. Beispielsweise w\u00fcrde die beiden o. g. Beispiele mit einer verketteten Liste deutlich l\u00e4nger ben\u00f6tigen als mit einem Array \u2013 an der Komplexit\u00e4tsklasse \u00e4ndert das jedoch nichts.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"o-n-beispiel-quellcode\">O(n) Beispiel-Quellcode<\/h4>\n\n\n\n<p>Der folgende Quellcode (Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/simple\/LinearTimeSimpleDemo.java\" target=\"_blank\">LinearTimeSimpleDemo<\/a>) misst den Aufwand f\u00fcr das Summieren aller Elemente eines Arrays:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">main<\/span><span class=\"hljs-params\">(String&#091;] args)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> n = <span class=\"hljs-number\">32<\/span>; n &lt;= <span class=\"hljs-number\">536_870_912<\/span>; n *= <span class=\"hljs-number\">2<\/span>) {\n    <span class=\"hljs-keyword\">int<\/span>&#091;] array = createArrayOfSize(n);\n\n    <span class=\"hljs-keyword\">long<\/span> sum = <span class=\"hljs-number\">0<\/span>;\n\n    <span class=\"hljs-keyword\">long<\/span> time = System.nanoTime();\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; n; i++) {\n      sum += array&#091;i];\n    }\n    time = System.nanoTime() - time;\n\n    System.out.printf(<span class=\"hljs-string\">\"n = %d -&gt; time = %d ns%n\"<\/span>, n, time);\n  }\n}\n\n<span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;] createArrayOfSize(<span class=\"hljs-keyword\">int<\/span> n) {\n  <span class=\"hljs-keyword\">int<\/span>&#091;] array = <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;n];\n  <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; n; i++) {\n    array&#091;i] = i;\n  }\n  <span class=\"hljs-keyword\">return<\/span> array;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Auf meinem System steigt die ben\u00f6tigte Zeit von 1.100 ns auf 155.911.900 ns ungef\u00e4hr linear an. Bessere Messergebnisse liefert auch hier das Testprogramm <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/TimeComplexityDemo.java\" target=\"_blank\">TimeComplexityDemo<\/a> mit der Algorithmus-Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/problem\/LinearTime.java\" target=\"_blank\">LinearTime<\/a> \u2013 hier ein Auszug der Ergebnisse:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-5\" data-shcb-language-name=\"Klartext\" data-shcb-language-slug=\"plaintext\"><span><code class=\"hljs language-plaintext\">--- LinearTime (results 5 of 5) ---\nLinearTime, n =         512 -&gt; fastest:         300 ns, median:         300 ns\nLinearTime, n =     524,288 -&gt; fastest:     159,300 ns, median:     189,400 ns\nLinearTime, n = 536,870,912 -&gt; fastest: 164,322,600 ns, median: 168,681,700 ns<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-5\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Klartext<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">plaintext<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die vollst\u00e4ndigen Testergebnisse findest du auch hier wieder in <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/test-results.txt\" target=\"_blank\">test-results.txt<\/a>.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"was-ist-der-unterschied-zwischen-linear-und-proportional\">Was ist der Unterschied zwischen \"linear\" und \"proportional\"?<\/h4>\n\n\n\n<p>Eine Funktion ist <em>linear<\/em>, wenn sie durch eine gerade Linie dargestellt weden kann, z. B. <em>f(x) = 5x + 3<\/em>. <\/p>\n\n\n\n<p><em>Proportional<\/em> ist ein Sonderfall von <em>linear<\/em>, bei dem die Linie durch den Punkt (0,0) des Koordinatensystems geht, z. B. <em>f(x) = 3x<\/em>.<\/p>\n\n\n\n<p>Da es in der Klasse <em>O(n)<\/em> einen konstanten Anteil geben kann, handelt es sich um <em>linearen<\/em> Aufwand.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"o-n\u00b2-quadratischer-aufwand\">O(n\u00b2) \u2013 quadratischer Aufwand<\/h3>\n\n\n\n<p>Ausgesprochen: \"O von n Quadrat\"<\/p>\n\n\n\n<p>Der Aufwand w\u00e4chst quadratisch mit der Anzahl der Eingabeelemente: Verdoppelt sich die Anzahl der Eingabeelemente <em>n<\/em>, dann vervierfacht sich in etwa der Aufwand. (Und verzehnfacht sich die Anzahl der Elemente, w\u00e4chst die ben\u00f6tigte Zeit um den Faktor Hundert!)<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"412\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on\u00b2-quadratischer-aufwand-800x412.png\" alt=\"Komplexit\u00e4tsklasse O(n\u00b2) \u2013 quadratischer Aufwand\" class=\"wp-image-12713\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on\u00b2-quadratischer-aufwand-800x412.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on\u00b2-quadratischer-aufwand-224x115.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on\u00b2-quadratischer-aufwand-336x173.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on\u00b2-quadratischer-aufwand-504x259.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on\u00b2-quadratischer-aufwand-672x346.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on\u00b2-quadratischer-aufwand-400x206.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on\u00b2-quadratischer-aufwand-600x309.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on\u00b2-quadratischer-aufwand-944x486.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on\u00b2-quadratischer-aufwand-1200x617.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on\u00b2-quadratischer-aufwand.png 1520w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\" id=\"o-n\u00b2-beispiele\">O(n\u00b2) Beispiele <\/h4>\n\n\n\n<p>Beispiele f\u00fcr quadratischen Aufwand sind einfache Sortieralgorithmen wie <a href=\"\/de\/algorithmen\/insertion-sort\/\">Insertion Sort<\/a>, <a href=\"\/de\/algorithmen\/selection-sort\/\">Selection Sort<\/a> und <a href=\"\/de\/algorithmen\/bubble-sort\/\">Bubble Sort<\/a>.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"o-n\u00b2-beispiel-quellcode\">O(n\u00b2) Beispiel-Quellcode<\/h4>\n\n\n\n<p>Das folgende Beispiel (<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/simple\/QuadraticTimeSimpleDemo.java\" target=\"_blank\">QuadraticTimeSimpleDemo<\/a>) zeigt, wie sich der Aufwand f\u00fcr das Sortieren eines Arrays mittels <em>Insertion Sort<\/em> in Abh\u00e4ngigkeit von der Gr\u00f6\u00dfe des Arrays \u00e4ndert:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-6\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">main<\/span><span class=\"hljs-params\">(String&#091;] args)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> n = <span class=\"hljs-number\">32<\/span>; n &lt;= <span class=\"hljs-number\">262_144<\/span>; n *= <span class=\"hljs-number\">2<\/span>) {\n    <span class=\"hljs-keyword\">int<\/span>&#091;] array = createRandomArrayOfSize(n);\n\n    <span class=\"hljs-keyword\">long<\/span> time = System.nanoTime();\n    insertionSort(array);\n    time = System.nanoTime() - time;\n\n    System.out.printf(<span class=\"hljs-string\">\"n = %d -&gt; time = %d ns%n\"<\/span>, n, time);\n  }\n}\n\n<span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;] createRandomArrayOfSize(<span class=\"hljs-keyword\">int<\/span> n) {\n  ThreadLocalRandom random = ThreadLocalRandom.current();\n  <span class=\"hljs-keyword\">int<\/span>&#091;] array = <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;n];\n  <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; n; i++) {\n    array&#091;i] = random.nextInt();\n  }\n  <span class=\"hljs-keyword\">return<\/span> array;\n}\n\n<span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">insertionSort<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">1<\/span>; i &lt; elements.length; i++) {\n    <span class=\"hljs-keyword\">int<\/span> elementToSort = elements&#091;i];\n    <span class=\"hljs-keyword\">int<\/span> j = i;\n    <span class=\"hljs-keyword\">while<\/span> (j &gt; <span class=\"hljs-number\">0<\/span> &amp;&amp; elementToSort &lt; elements&#091;j - <span class=\"hljs-number\">1<\/span>]) {\n      elements&#091;j] = elements&#091;j - <span class=\"hljs-number\">1<\/span>];\n      j--;\n    }\n    elements&#091;j] = elementToSort;\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-6\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Bessere Messergebnisse bekommt man wiederum mit dem Testprogramm&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/TimeComplexityDemo.java\" target=\"_blank\">TimeComplexityDemo<\/a>&nbsp;und der Klasse&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/problem\/QuadraticTime.java\" target=\"_blank\">QuadraticTime<\/a>. Hier der Auszug der Ergebnisse, bei dem man sch\u00f6n die jeweilige ungef\u00e4hre Vervierfachung der Zeit bei Verdoppelung der Problemgr\u00f6\u00dfe erkennen kann:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-7\" data-shcb-language-name=\"Klartext\" data-shcb-language-slug=\"plaintext\"><span><code class=\"hljs language-plaintext\">QuadraticTime, n =   8,192 -&gt; fastest:     4,648,400 ns, median:     4,720,200 ns\nQuadraticTime, n =  16,384 -&gt; fastest:    19,189,100 ns, median:    19,440,400 ns\nQuadraticTime, n =  32,768 -&gt; fastest:    78,416,700 ns, median:    79,896,000 ns\nQuadraticTime, n =  65,536 -&gt; fastest:   319,905,300 ns, median:   330,530,600 ns\nQuadraticTime, n = 131,072 -&gt; fastest: 1,310,702,600 ns, median: 1,323,919,500 ns<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-7\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Klartext<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">plaintext<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die vollst\u00e4ndigen Testergebnisse findest du in&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/test-results.txt\" target=\"_blank\">test-results.txt<\/a>.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"o-n-vs-o-n\u00b2\">O(n) vs. O(n\u00b2)<\/h4>\n\n\n\n<p>An dieser Stelle m\u00f6chte ich noch einmal darauf hinweisen, dass der Aufwand Komponenten niedrigerer Komplexit\u00e4tsklassen und konstante Faktoren enthalten kann. Beides ist f\u00fcr die O-Notation irrelevant, da diese bei hinreichend gro\u00dfem <em>n<\/em> nicht mehr ins Gewicht fallen.<\/p>\n\n\n\n<p>Es kann somit auch sein, dass beispielsweise <em>O(n\u00b2)<\/em> schneller ist als <em>O(n)<\/em> \u2013 zumindest bis zu einer gewissen Gr\u00f6\u00dfe von <em>n<\/em>. <\/p>\n\n\n\n<p>Im folgenden Beispiel-Diagramm werden drei fiktive Algorithmen gegen\u00fcbergestellt: einer mit der Komplexit\u00e4tsklasse <em>O(n\u00b2)<\/em> und zwei mit <em>O(n)<\/em>, wobei einer davon schneller ist als der andere. Es ist gut zu sehen, wie bis zu <em>n = 4<\/em> der orangene <em>O(n\u00b2)<\/em>-Algorithmus weniger Zeit ben\u00f6tigt als der gelbe <em>O(n)<\/em>-Algorithmus. Und sogar bis <em>n = 8<\/em> weniger Zeit als der t\u00fcrkise <em>O(n)<\/em>-Algorithmus.<\/p>\n\n\n\n<p>Ab hinreichend gro\u00dfem <em>n<\/em> \u2013 also ab <em>n = 9<\/em> \u2013 ist und bleibt <em>O(n\u00b2)<\/em> der langsamste Algorithmus.<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"412\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-vs-on\u00b2-v2-800x412.png\" alt=\"O-Notation - Vergleich der Komplexit\u00e4tsklassen O(n) und O(n\u00b2)\" class=\"wp-image-12582\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-vs-on\u00b2-v2-800x412.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-vs-on\u00b2-v2-224x115.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-vs-on\u00b2-v2-336x173.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-vs-on\u00b2-v2-504x259.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-vs-on\u00b2-v2-672x346.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-vs-on\u00b2-v2-400x206.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-vs-on\u00b2-v2-600x309.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-vs-on\u00b2-v2-944x486.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-vs-on\u00b2-v2-1200x617.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on-vs-on\u00b2-v2.png 1520w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure>\n<\/div>\n\n\n<p>Als n\u00e4chstes kommen wir zu zwei nicht ganz so intuitiv verst\u00e4ndlichen Komplexit\u00e4tsklassen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"o-log-n-logarithmischer-aufwand\">O(log n) \u2013 logarithmischer Aufwand<\/h3>\n\n\n\n<p>Ausgesprochen: \"O von log n\"<\/p>\n\n\n\n<p>Der Aufwand w\u00e4chst ungef\u00e4hr um einen konstanten Betrag, wenn sich die Anzahl der Eingabeelemente verdoppelt. <\/p>\n\n\n\n<p>Wenn sich beispielsweise der Aufwand um eine Sekunde erh\u00f6ht, wenn die Anzahl der Eingabeelemente von 1.000 auf 2.000 steigt, dann erh\u00f6ht er sich lediglich um eine weitere Sekunde, wenn der Aufwand auf 4.000 steigt und wiederum um eine weitere Sekunde, wenn der Aufwand auf 8.000 steigt.<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"412\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-olog_n-logarithmischer-aufwand-v2-800x412.png\" alt=\"Komplexit\u00e4tsklasse O(n\u00b2) \u2013 logarithmischer Aufwand\" class=\"wp-image-12561\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-olog_n-logarithmischer-aufwand-v2-800x412.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-olog_n-logarithmischer-aufwand-v2-224x115.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-olog_n-logarithmischer-aufwand-v2-336x173.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-olog_n-logarithmischer-aufwand-v2-504x259.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-olog_n-logarithmischer-aufwand-v2-672x346.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-olog_n-logarithmischer-aufwand-v2-400x206.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-olog_n-logarithmischer-aufwand-v2-600x309.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-olog_n-logarithmischer-aufwand-v2-944x486.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-olog_n-logarithmischer-aufwand-v2-1200x617.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-olog_n-logarithmischer-aufwand-v2.png 1520w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\" id=\"o-log-n-beispiel\">O(log n) Beispiel<\/h4>\n\n\n\n<p>Ein Beispiel f\u00fcr logarithmischen Aufwand ist die <a href=\"\/de\/algorithmen\/binaere-suche-java\/\">bin\u00e4re Suche<\/a> nach einem bestimmten Element in einem sortierten Array der Gr\u00f6\u00dfe <em>n<\/em>. <\/p>\n\n\n\n<p>Da wir mit jedem Suchschritt den zu durchsuchenden Bereich halbieren, k\u00f6nnen wir im Umkehrschluss mit nur einem Suchschritt mehr ein doppelt so gro\u00dfes Array durchsuchen. <\/p>\n\n\n\n<p>(Die \u00e4lteren unter uns kennen das vielleicht noch von der Suche im Telefonbuch oder in einem Lexikon.)<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"o-log-n-beispiel-quellcode\">O(log n) Beispiel-Quellcode<\/h4>\n\n\n\n<p>Das folgende Beispiel (<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/simple\/LogarithmicTimeSimpleDemo.java\" target=\"_blank\">LogarithmicTimeSimpleDemo<\/a>) misst, wie sich der Aufwand f\u00fcr die bin\u00e4re Suche innerhalb eines sortierten Arrays im Verh\u00e4ltnis zur Gr\u00f6\u00dfe des Arrays ver\u00e4ndert:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-8\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">main<\/span><span class=\"hljs-params\">(String&#091;] args)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> n = <span class=\"hljs-number\">32<\/span>; n &lt;= <span class=\"hljs-number\">536_870_912<\/span>; n *= <span class=\"hljs-number\">2<\/span>) {\n    <span class=\"hljs-keyword\">int<\/span>&#091;] array = createArrayOfSize(n);\n\n    <span class=\"hljs-keyword\">long<\/span> time = System.nanoTime();\n    Arrays.binarySearch(array, <span class=\"hljs-number\">0<\/span>);\n    time = System.nanoTime() - time;\n\n    System.out.printf(<span class=\"hljs-string\">\"n = %d -&gt; time = %d ns%n\"<\/span>, n, time);\n  }\n}\n\n<span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;] createArrayOfSize(<span class=\"hljs-keyword\">int<\/span> n) {\n  <span class=\"hljs-keyword\">int<\/span>&#091;] array = <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;n];\n  <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; n; i++) {\n    array&#091;i] = i;\n  }\n  <span class=\"hljs-keyword\">return<\/span> array;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-8\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Bessere Messergebnisse bekommen wir, wie zuvor, mit dem Testprogramm&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/TimeComplexityDemo.java\" target=\"_blank\">TimeComplexityDemo<\/a>&nbsp;und der Klasse&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/problem\/LogarithmicTime.java\" target=\"_blank\">LogarithmicTime<\/a>.&nbsp;Hier die Ergebnisse:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-9\" data-shcb-language-name=\"Klartext\" data-shcb-language-slug=\"plaintext\"><span><code class=\"hljs language-plaintext\">LogarithmicTime, n =          32 -&gt; fastest:  77,800 ns, median: 107,200 ns\nLogarithmicTime, n =       2,048 -&gt; fastest: 173,500 ns, median: 257,400 ns\nLogarithmicTime, n =     131,072 -&gt; fastest: 363,400 ns, median: 413,100 ns\nLogarithmicTime, n =   8,388,608 -&gt; fastest: 661,100 ns, median: 670,800 ns\nLogarithmicTime, n = 536,870,912 -&gt; fastest: 770,500 ns, median: 875,700 ns<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-9\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Klartext<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">plaintext<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die Problemgr\u00f6\u00dfe <em>n<\/em> w\u00e4chst hier jeweils um den Faktor 64. Der Aufwand w\u00e4chst nicht immer exakt um den gleichen Wert, aber doch ausreichend genau, um zu demonstrieren, dass logarithmischer Aufwand deutlich g\u00fcnstiger ist als linearer Aufwand (bei welchem die ben\u00f6tigte Zeit auch jeweils um den Faktor 64 wachsen w\u00fcrde).<\/p>\n\n\n\n<p>Die vollst\u00e4ndigen Testergebnisse findest Du, wie auch zuvor, in der Datei&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/test-results.txt\" target=\"_blank\">test-results.txt<\/a>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"o-n-log-n-quasi-linearer-aufwand\">O(n log n) \u2013 quasi-linearer Aufwand<\/h3>\n\n\n\n<p>Ausgesprochen: \"O von n log n\"<\/p>\n\n\n\n<p>Der Aufwand w\u00e4chst etwas st\u00e4rker als linear, da die lineare Komponente mit einer logarithmischen multipliziert wird; man kann zum besseren Verst\u00e4ndnis auch ein Multiplikationszeichen einf\u00fcgen: <em>O(n&nbsp;\u00d7&nbsp;log&nbsp;n)<\/em>. <\/p>\n\n\n\n<p>Am besten l\u00e4sst sich das am Graphen veranschaulichen. Wir haben hier eine Kurve, deren Steigung zu Beginn noch sichtbar w\u00e4chst, mit wachsendem <em>n<\/em> sich aber einer Geraden ann\u00e4hert:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"412\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on_log_n-quasi-linearer-aufwand-v2-800x412.png\" alt=\"Komplexit\u00e4tsklasse O(n log n) \u2013 quasi-linearer Aufwand\" class=\"wp-image-12564\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on_log_n-quasi-linearer-aufwand-v2-800x412.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on_log_n-quasi-linearer-aufwand-v2-224x115.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on_log_n-quasi-linearer-aufwand-v2-336x173.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on_log_n-quasi-linearer-aufwand-v2-504x259.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on_log_n-quasi-linearer-aufwand-v2-672x346.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on_log_n-quasi-linearer-aufwand-v2-400x206.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on_log_n-quasi-linearer-aufwand-v2-600x309.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on_log_n-quasi-linearer-aufwand-v2-944x486.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on_log_n-quasi-linearer-aufwand-v2-1200x617.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-komplexitaetsklasse-on_log_n-quasi-linearer-aufwand-v2.png 1520w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\" id=\"o-n-log-n-beispiel\">O(n log n) Beispiel<\/h4>\n\n\n\n<p>Als Beispiele f\u00fcr quasi-linearen Aufwand k\u00f6nnen effiziente Sortieralgorithmen wie <a href=\"\/de\/algorithmen\/quicksort\/\">Quicksort<\/a>, <a href=\"\/de\/algorithmen\/mergesort\/\">Mergesort<\/a> und <a href=\"\/de\/algorithmen\/heapsort\/\">Heapsort<\/a> genannt werden.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"o-n-log-n-beispiel-quellcode\">O(n log n) Beispiel-Quellcode<\/h4>\n\n\n\n<p>Der folgende Beispiel-Code (Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/simple\/QuasiLinearTimeSimpleDemo.java\" target=\"_blank\">QuasiLinearTimeSimpleDemo<\/a>) zeigt, wie sich der Aufwand f\u00fcr das <a href=\"\/de\/algorithmen\/sortieren-in-java\/\">Sortieren eines Arrays<\/a> mit Quicksort\u00b3 im Verh\u00e4ltnis zur Array-Gr\u00f6\u00dfe \u00e4ndert:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-10\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">main<\/span><span class=\"hljs-params\">(String&#091;] args)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> n = <span class=\"hljs-number\">64<\/span>; n &lt;= <span class=\"hljs-number\">67_108_864<\/span>; n *= <span class=\"hljs-number\">2<\/span>) {\n    <span class=\"hljs-keyword\">int<\/span>&#091;] array = createRandomArrayOfSize(n);\n\n    <span class=\"hljs-keyword\">long<\/span> time = System.nanoTime();\n    Arrays.sort(array);\n    time = System.nanoTime() - time;\n\n    System.out.printf(<span class=\"hljs-string\">\"n = %d -&gt; time = %d ns%n\"<\/span>, n, time);\n  }\n}\n\n<span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;] createRandomArrayOfSize(<span class=\"hljs-keyword\">int<\/span> n) {\n  ThreadLocalRandom random = ThreadLocalRandom.current();\n  <span class=\"hljs-keyword\">int<\/span>&#091;] array = <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;n];\n  <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; n; i++) {\n    array&#091;i] = random.nextInt();\n  }\n  <span class=\"hljs-keyword\">return<\/span> array;\n}\n<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-10\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Genauer wird es wieder mit dem Testprogramm&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/TimeComplexityDemo.java\" target=\"_blank\">TimeComplexityDemo<\/a>&nbsp;und der Klasse&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/src\/eu\/happycoders\/o\/problem\/QuasiLinearTime.java\" target=\"_blank\">QuasiLinearTime<\/a>.&nbsp;Hier ein Auszug der Ergebnisse:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-11\" data-shcb-language-name=\"Klartext\" data-shcb-language-slug=\"plaintext\"><span><code class=\"hljs language-plaintext\">QuasiLinearTime, n =        256 -&gt; fastest:        12,200 ns, med.:        12,500 ns\nQuasiLinearTime, n =      4,096 -&gt; fastest:       228,600 ns, med.:       234,200 ns\nQuasiLinearTime, n =     65,536 -&gt; fastest:     4,606,500 ns, med.:     4,679,800 ns\nQuasiLinearTime, n =  1,048,576 -&gt; fastest:    93,933,500 ns, med.:    95,216,300 ns\nQuasiLinearTime, n = 16,777,216 -&gt; fastest: 1,714,541,900 ns, med.: 1,755,715,000 ns<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-11\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Klartext<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">plaintext<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die Problemgr\u00f6\u00dfe steigt hier jeweils um den Faktor 16 und die ben\u00f6tigte Zeit um Faktor 18,5 bis 20,3. Das vollst\u00e4ndige Testergebnis findest du, wie immer, in <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/o-notation-and-time-complexity\/blob\/main\/test-results.txt\" target=\"_blank\">test-results.txt<\/a>.<\/p>\n\n\n\n<p class=\"has-very-light-gray-background-color has-background\">\u00b3 Genauer gesagt: Dual-Pivot Quicksort, welches bei Arrays mit weniger als 44 Elementen auf Insertion Sort wechselt. Aus diesem Grund startet dieser Test bei 64 Elementen, nicht bei 32 wie die anderen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"o-notation-reihenfolge\">O-Notation Reihenfolge<\/h3>\n\n\n\n<p>Hier noch einmal die vorgestellten Komplexit\u00e4tsklassen, aufsteigend sortiert nach Komplexit\u00e4t:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><em>O(1)<\/em> \u2013 konstanter Aufwand<\/li>\n\n\n\n<li><em>O(log n)<\/em> \u2013 logarithmischer Aufwand<\/li>\n\n\n\n<li><em>O(n)<\/em> \u2013 linearer Aufwand<\/li>\n\n\n\n<li><em>O(n log n)<\/em> \u2013 quasi-linearer Aufwand<\/li>\n\n\n\n<li><em>O(n\u00b2)<\/em> \u2013 quadratischer Aufwand<\/li>\n<\/ul>\n\n\n\n<p>Und hier der Vergleich in graphischer Darstellung:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"412\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-v3-800x412.png\" alt=\"O-Notation \u2013 Vergleich der Komplexit\u00e4tsklassen O(1), O(log n), O(n), O(n log n), O(n\u00b2)\" class=\"wp-image-12736\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-v3-800x412.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-v3-224x115.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-v3-336x173.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-v3-504x259.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-v3-672x346.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-v3-400x206.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-v3-600x309.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-v3-944x486.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-v3-1200x617.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-v3.png 1520w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure>\n<\/div>\n\n\n<p>Ich habe die Kurven absichtlich so entlang der Aufwandsachse verschoben, dass die schlechteste Komplexit\u00e4tsklasse <em>O(n\u00b2)<\/em> bei niedrigem <em>n<\/em> am schnellsten ist und die beste Komplexit\u00e4tsklasse <em>O(1)<\/em> am langsamsten. Um dann zu zeigen, wie sich f\u00fcr hinreichend hohe Werte von <em>n<\/em> die Aufw\u00e4nde entsprechend den Erwartungen verschieben.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"weitere-komplexitatsklassen\">Weitere Komplexit\u00e4tsklassen<\/h3>\n\n\n\n<p>Weitere Komplexit\u00e4tsklassen sind z. B. <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><em>O(n<sup>m<\/sup>)<\/em> \u2013 polynomieller Aufwand<\/li>\n\n\n\n<li><em>O(2<sup>n<\/sup>)<\/em> \u2013 exponentieller Aufwand<\/li>\n\n\n\n<li><em>O(n!)<\/em> \u2013 faktorieller Aufwand<\/li>\n<\/ul>\n\n\n\n<p>Diese sind jedoch so schlecht, dass wir Algorithmen mit diesen Komplexit\u00e4ten m\u00f6glichst vermeiden sollten.<\/p>\n\n\n\n<p>Im folgenden Diagram habe ich diese Klassen noch einmal mit aufgenommen (f\u00fcr <em>O(n<sup>m<\/sup>)<\/em> mit <em>m=3<\/em>):<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"413\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-erweitert-800x413.png\" alt=\"O-Notation \u2013 Vergleich der Komplexit\u00e4tsklassen O(1), O(log n), O(n), O(n log n), O(n\u00b2), O(n\u00b3), O(2\u207f), O(n!)\" class=\"wp-image-12500\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-erweitert-800x413.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-erweitert-224x116.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-erweitert-336x173.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-erweitert-504x260.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-erweitert-672x347.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-erweitert-400x206.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-erweitert-600x309.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-erweitert-944x487.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-erweitert-1200x619.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-vergleich-komplexitaetsklassen-erweitert.png 1520w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><\/figure>\n<\/div>\n\n\n<p>Die y-Achse musste ich hier im Vergleich zum vorherigen Diagramm um Faktor 10 stauchen, damit ich die drei zus\u00e4tzlichen Kurven sinnvoll abbilden konnte.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"fazit\">Fazit<\/h2>\n\n\n\n<p>Zeitkomplexit\u00e4t beschreibt, wie sich die Laufzeit eines Algorithmus in Abh\u00e4ngigkeit von der Menge der Eingabedaten ver\u00e4ndert. Die gebr\u00e4uchlichsten Komplexit\u00e4tsklassen sind (aufsteigend sortiert nach Aufwand): <em>O(1)<\/em>, <em>O(log n)<\/em>, <em>O(n)<\/em>, <em>O(n log n)<\/em>, <em>O(n\u00b2)<\/em>. <\/p>\n\n\n\n<p>Algorithmen mit konstantem, logarithmischem, linearem und quasi-linearem Aufwand f\u00fchren in der Regel bei Eingabegr\u00f6\u00dfen bis zu mehreren Milliarden Elementen in \u00fcberschaubarer Zeit zu einem Ende, w\u00e4hrend Algorithmen mit quadratischem Aufwand f\u00fcr dieselben Eingabemengen schnell theoretische Ausf\u00fchrungszeiten von mehreren Jahren erreichen k\u00f6nnen\u2074. Sie sollten also, soweit wie m\u00f6glich, vermieden werden.<\/p>\n\n\n\n<p class=\"has-very-light-gray-background-color has-background\">\u2074 Quicksort beispielsweise sortiert auf meinem Laptop eine Milliarde Elemente in 90 Sekunden; Insertion Sort hingegen braucht f\u00fcr eine <em>Million<\/em> Elemente 85 Sekunden; das w\u00e4ren auf eine Milliarde Elemente hochgerechnet 85 Millionen Sekunden \u2013 oder anders ausgedr\u00fcckt: etwas \u00fcber zwei Jahre und acht Monate!<\/p>\n<aside><p>Wenn dir der Artikel weitergeholfen hat, w\u00fcrde ich mich sehr \u00fcber eine positive Bewertung auf meinem <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">ProvenExpert-Profil<\/a> freuen. Dein Feedback hilft mir, meine Inhalte weiter zu verbessern und motiviert mich, neue informative Artikel zu schreiben.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">Bewertung abgeben<\/a><\/p>\r\n                        <p>M\u00f6chtest du auf dem Laufenden bleiben und informiert werden, wenn neue Artikel auf HappyCoders.eu ver\u00f6ffentlicht werden? Dann <a href=\"#\" data-formkit-toggle=\"d8ee997126\">klicke hier<\/a>, um dich f\u00fcr den HappyCoders-Newsletter anzumelden.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"#\" data-formkit-toggle=\"d8ee997126\">Newsletter-Anmeldung<\/a><\/p><\/aside>","protected":false},"excerpt":{"rendered":"<p>In diesem Artikel erkl\u00e4re ich die O-Notation und die damit beschriebene Zeit- und Platzkomplexit\u00e4t \u2013 ausschlie\u00dflich anhand von Beispielen und Diagrammen \u2013 und ganz ohne mathematische Formeln, Beweisf\u00fchrungen und Symbole wie \u03b8, \u03a9, \u03c9, \u2208, \u2200, \u2203 und \u03b5.<\/p>\n","protected":false},"author":1,"featured_media":19126,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_robots_primary_cat":"none","_seopress_titles_title":"","_seopress_titles_desc":"Anschauliche Erkl\u00e4rungen mit Beispielen und Diagrammen: O-Notationen f\u00fcr die Komplexit\u00e4tsklassen O(1), O(log n), O(n), O(n log n), O(n\u00b2)","_seopress_robots_index":"","_uag_custom_page_level_css":"","_wp_convertkit_post_meta":{"form":"-1","landing_page":"","tag":"0","restrict_content":"0"},"_metis_text_type":"standard","_metis_text_length":19040,"_post_count":0,"footnotes":""},"categories":[127],"tags":[136],"class_list":["post-12410","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-algorithmen-allgemein"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert.jpg",1200,675,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert.jpg",300,169,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert.jpg",768,432,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert.jpg",1024,576,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert-224x126.jpg",224,126,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert-336x189.jpg",336,189,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert-504x284.jpg",504,284,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert-672x378.jpg",672,378,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert-400x225.jpg",400,225,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert-600x338.jpg",600,338,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert-800x450.jpg",800,450,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert-944x531.jpg",944,531,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert.jpg",1200,675,false],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert.jpg",871,490,false],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert.jpg",1200,675,false],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert.jpg",1200,675,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/o-notation-zeitkomplexitaet-anschaulich-erklaert.jpg",1200,675,false]},"uagb_author_info":{"display_name":"Sven Woltmann","author_link":"https:\/\/www.happycoders.eu\/de\/author\/sven\/"},"uagb_comment_info":18,"uagb_excerpt":"In diesem Artikel erkl\u00e4re ich die O-Notation und die damit beschriebene Zeit- und Platzkomplexit\u00e4t \u2013 ausschlie\u00dflich anhand von Beispielen und Diagrammen \u2013 und ganz ohne mathematische Formeln, Beweisf\u00fchrungen und Symbole wie \u03b8, \u03a9, \u03c9, \u2208, \u2200, \u2203 und \u03b5.","public_identification_id":"9041f9e6249d4756a7386cf259278d1d","private_identification_id":"93a2e12996964156a90c9e30cf49abb6","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12410","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/comments?post=12410"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12410\/revisions"}],"predecessor-version":[{"id":52483,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12410\/revisions\/52483"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/19126"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=12410"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=12410"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=12410"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}