https://sibiwiki.de/wiki/index.php?action=history&feed=atom&title=Landau-Klassen 2026-04-13T14:42:00Z Versionsgeschichte dieser Seite in SibiWiki MediaWiki 1.37.1 https://sibiwiki.de/wiki/index.php?title=Landau-Klassen&diff=2389&oldid=prev 2016-11-28T15:30:10Z

<p><span dir="auto"><span class="autocomment">Wichtige Landau-Klassen</span></span></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="de"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Nächstältere Version</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Version vom 28. November 2016, 15:30 Uhr</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l58">Zeile 58:</td> <td colspan="2" class="diff-lineno">Zeile 58:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|&lt;b&gt;f&lt;/b&gt; wächst ungefähr auf das Vierfache, wenn sich das Argument verdoppelt</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|&lt;b&gt;f&lt;/b&gt; wächst ungefähr auf das Vierfache, wenn sich das Argument verdoppelt</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|Einfache Algorithmen zum Sortieren von &lt;b&gt;n&lt;/b&gt; Zahlen</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|Einfache Algorithmen zum Sortieren von &lt;b&gt;n&lt;/b&gt; Zahlen</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Selectionsort</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Selectionsort<ins style="font-weight: bold; text-decoration: none;">, Insertionsort</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|&lt;b&gt;f &amp;isin; O(n!)&lt;/b&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|&lt;b&gt;f &amp;isin; O(n!)&lt;/b&gt;</div></td></tr> </table>

Akaibel https://sibiwiki.de/wiki/index.php?title=Landau-Klassen&diff=2388&oldid=prev 2016-11-28T15:29:18Z

<p><span dir="auto"><span class="autocomment">Bestimmung von Landau-Klassen für Funktionen</span></span></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="de"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Nächstältere Version</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Version vom 28. November 2016, 15:29 Uhr</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l17">Zeile 17:</td> <td colspan="2" class="diff-lineno">Zeile 17:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>f(n) = n&lt;sup&gt;2&lt;/sup&gt; + 20.000 ϵ '''O(n&lt;sup&gt;2&lt;/sup&gt;)''', denn der Startaufwand von 20.000 wird ignoriert!</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>f(n) = n&lt;sup&gt;2&lt;/sup&gt; + 20.000 ϵ '''O(n&lt;sup&gt;2&lt;/sup&gt;)''', denn der Startaufwand von 20.000 wird ignoriert!</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>g(n) = 300 n&lt;sup&gt;2&lt;/sup&gt; ϵ '''O(n&lt;sup&gt;2&lt;/sup&gt;)''', denn man könnte einen 300mal so schnellen Computer nehmen und wäre wieder bei <del style="font-weight: bold; text-decoration: none;">n2</del>!</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>g(n) = 300 n&lt;sup&gt;2&lt;/sup&gt; ϵ '''O(n&lt;sup&gt;2&lt;/sup&gt;)''', denn man könnte einen 300mal so schnellen Computer nehmen und wäre wieder bei <ins style="font-weight: bold; text-decoration: none;">n&lt;sup&gt;2&lt;/sup&gt;</ins>!</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>h(n) = n&lt;sup&gt;2&lt;/sup&gt; + 80n ϵ '''O(n&lt;sup&gt;2&lt;/sup&gt;)''', denn für große n ist 80n kleiner als n&lt;sup&gt;2&lt;/sup&gt; !</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>h(n) = n&lt;sup&gt;2&lt;/sup&gt; + 80n ϵ '''O(n&lt;sup&gt;2&lt;/sup&gt;)''', denn für große n ist 80n kleiner als n&lt;sup&gt;2&lt;/sup&gt; !</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"> </del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=Wichtige Landau-Klassen=</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>=Wichtige Landau-Klassen=</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{| class=&quot;wikitable&quot;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{| class=&quot;wikitable&quot;</div></td></tr> </table>

Akaibel https://sibiwiki.de/wiki/index.php?title=Landau-Klassen&diff=2387&oldid=prev 2016-11-28T15:28:41Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="de"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Nächstältere Version</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Version vom 28. November 2016, 15:28 Uhr</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2">Zeile 2:</td> <td colspan="2" class="diff-lineno">Zeile 2:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Kategorie:Algorithmen]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Kategorie:Algorithmen]]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Landau-Klassen werden in der Informatik verwendet, um das [[Laufzeitverhalten <del style="font-weight: bold; text-decoration: none;">von Algorithmen|Laufzeit </del>von Algorithmen]](z.B. Sortieralgorithmen) zu beschreiben.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Landau-Klassen werden in der Informatik verwendet, um das [[<ins style="font-weight: bold; text-decoration: none;">Laufzeit_von_Algorithmen|</ins>Laufzeitverhalten von Algorithmen]] (z.B. Sortieralgorithmen) zu beschreiben.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Die Landau-Klassen werden durch ein '''O''' gekennzeichnet, z.B. '''O'''(n&lt;sup&gt;2&lt;/sup&gt;)</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Die Landau-Klassen werden durch ein '''O''' gekennzeichnet, z.B. '''O'''(n&lt;sup&gt;2&lt;/sup&gt;)</div></td></tr> </table>

Akaibel https://sibiwiki.de/wiki/index.php?title=Landau-Klassen&diff=2386&oldid=prev 2016-11-28T15:27:35Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="de"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Nächstältere Version</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Version vom 28. November 2016, 15:27 Uhr</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2">Zeile 2:</td> <td colspan="2" class="diff-lineno">Zeile 2:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Kategorie:Algorithmen]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Kategorie:Algorithmen]]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>Landau-Klassen werden in der Informatik verwendet, um das Laufzeitverhalten von Algorithmen (z.B. Sortieralgorithmen) zu beschreiben.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>Landau-Klassen werden in der Informatik verwendet, um das <ins style="font-weight: bold; text-decoration: none;">[[</ins>Laufzeitverhalten von Algorithmen<ins style="font-weight: bold; text-decoration: none;">|Laufzeit von Algorithmen]]</ins>(z.B. Sortieralgorithmen) zu beschreiben.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Die Landau-Klassen werden durch ein '''O''' gekennzeichnet, z.B. '''O'''(n&lt;sup&gt;2&lt;/sup&gt;)</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Die Landau-Klassen werden durch ein '''O''' gekennzeichnet, z.B. '''O'''(n&lt;sup&gt;2&lt;/sup&gt;)</div></td></tr> </table>

Akaibel https://sibiwiki.de/wiki/index.php?title=Landau-Klassen&diff=2015&oldid=prev 2015-09-15T10:40:49Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="de"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Nächstältere Version</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Version vom 15. September 2015, 10:40 Uhr</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Zeile 1:</td> <td colspan="2" class="diff-lineno">Zeile 1:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Kategorie:Informatik]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Kategorie:Informatik]]</div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[Kategorie:Algorithmen]]</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Landau-Klassen werden in der Informatik verwendet, um das Laufzeitverhalten von Algorithmen (z.B. Sortieralgorithmen) zu beschreiben.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>Landau-Klassen werden in der Informatik verwendet, um das Laufzeitverhalten von Algorithmen (z.B. Sortieralgorithmen) zu beschreiben.</div></td></tr> </table>

Akaibel https://sibiwiki.de/wiki/index.php?title=Landau-Klassen&diff=1505&oldid=prev 2014-06-05T08:25:57Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="de"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Nächstältere Version</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Version vom 5. Juni 2014, 08:25 Uhr</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Zeile 1:</td> <td colspan="2" class="diff-lineno">Zeile 1:</td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[Kategorie:Informatik]]</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Landau-Klassen werden in der Informatik verwendet, um das Laufzeitverhalten von Algorithmen (z.B. Sortieralgorithmen) zu beschreiben.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Die Landau-Klassen werden durch ein '''O''' gekennzeichnet, z.B. '''O'''(n&lt;sup>2&lt;/sup>)</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">=Idee=</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Die Grundidee der Landau-Klassen besteht darin, die Laufzeit von Algorithmen abschätzen zu können, und zwar</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* unabhängig von der Rechenleistung des Computers, auf dem sie laufen</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* unabhängig von der Dauer einer einzelnen Rechenoperation, d.h. jede Operation gilt als gleich "teuer".</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* unabhängig von einem einmaligen "Startaufwand" (bzw. "Schlussaufwand") zu Beginn (bzw. am Ende) eines Algorithmus</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">=Bestimmung von Landau-Klassen für Funktionen=</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Das "Berechnen" der Laufzeit von Algorithmen wird dadurch radikal vereinfacht, z.B.:</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">f(n) = n&lt;sup>2&lt;/sup> + 20.000 ϵ '''O(n&lt;sup>2&lt;/sup>)''', denn der Startaufwand von 20.000 wird ignoriert!</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">g(n) = 300 n&lt;sup>2&lt;/sup> ϵ '''O(n&lt;sup>2&lt;/sup>)''', denn man könnte einen 300mal so schnellen Computer nehmen und wäre wieder bei n2!</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">h(n) = n&lt;sup>2&lt;/sup> + 80n ϵ '''O(n&lt;sup>2&lt;/sup>)''', denn für große n ist 80n kleiner als n&lt;sup>2&lt;/sup> !</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"> </ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">=Wichtige Landau-Klassen=</ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{| class=&quot;wikitable&quot;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>{| class=&quot;wikitable&quot;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>|-</div></td></tr> </table>

Akaibel https://sibiwiki.de/wiki/index.php?title=Landau-Klassen&diff=1504&oldid=prev 2014-06-05T08:17:48Z

<p>Die Seite wurde neu angelegt: „{| class=&quot;wikitable&quot; |- ! Notation ! Bedeutung ! Anschauliche Erklärung ! Beispiele für Laufzeiten |- |&lt;b&gt;f ∈ O(1)&lt;/b&gt; |&lt;b&gt;f&lt;/b&gt; ist beschränkt |&lt;b&gt;f&lt;/…“</p> <p><b>Neue Seite</b></p><div>{| class=&quot;wikitable&quot;<br /> |-<br /> ! Notation<br /> ! Bedeutung<br /> ! Anschauliche Erklärung<br /> ! Beispiele für Laufzeiten<br /> |-<br /> |&lt;b&gt;f &amp;isin; O(1)&lt;/b&gt;<br /> |&lt;b&gt;f&lt;/b&gt; ist beschränkt<br /> |&lt;b&gt;f&lt;/b&gt; überschreitet einen konstanten Wert nicht (unabhängig vom Wert des Arguments).<br /> |Nachschlagen des &lt;b&gt;n&lt;/b&gt;-ten Elementes in einem Feld.<br /> |-<br /> |&lt;b&gt;f &amp;isin; O(log n)&lt;/b&gt;<br /> |&lt;b&gt;f&lt;/b&gt; wächst logarithmisch<br /> |&lt;b&gt;f&lt;/b&gt; wächst ungefähr um einen konstanten Betrag, wenn sich das Argument verdoppelt.<br /> <br /> Die Basis des Logarithmus ist dabei egal.<br /> |Binäre Suche im sortierten Feld mit &lt;b&gt;n&lt;/b&gt; Einträgen<br /> |-<br /> |&lt;b&gt;f &amp;isin; O(n)&lt;/b&gt;<br /> |&lt;b&gt;f&lt;/b&gt; wächst Lineare Funktion|linear<br /> |&lt;b&gt;f&lt;/b&gt; wächst ungefähr auf das Doppelte, wenn sich das Argument verdoppelt.<br /> |Suche im unsortierten Feld mit &lt;b&gt;n&lt;/b&gt; Einträgen (Bsp. Lineare Suche)<br /> |-<br /> |&lt;b&gt;f &amp;isin;<br /> <br /> O(n &amp;lowast; log n)&lt;/b&gt;<br /> |&lt;b&gt;f&lt;/b&gt; hat super-lineares Wachstum<br /> |<br /> ||Fortgeschrittenere Algorithmen zum Sortieren von &lt;b&gt;n&lt;/b&gt; Zahlen<br /> Mergesort, Quicksort (im Average Case)<br /> |-<br /> |&lt;b&gt;f &amp;isin; O(n&lt;sup&gt;2&lt;/sup&gt;)&lt;/b&gt;<br /> |&lt;b&gt;f&lt;/b&gt; wächst Quadratische Funktion|quadratisch<br /> |&lt;b&gt;f&lt;/b&gt; wächst ungefähr auf das Vierfache, wenn sich das Argument verdoppelt<br /> |Einfache Algorithmen zum Sortieren von &lt;b&gt;n&lt;/b&gt; Zahlen<br /> Selectionsort<br /> |-<br /> |&lt;b&gt;f &amp;isin; O(n!)&lt;/b&gt;<br /> |&lt;b&gt;f&lt;/b&gt; wächst mit der Fakultät<br /> |&lt;b&gt;f&lt;/b&gt; wächst ungefähr auf das &lt;b&gt;(n+1)&lt;/b&gt;-fache, wenn sich das Argument um eins erhöht.<br /> ||Problem des Handlungsreisenden<br /> |}</div>

Akaibel