Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Zur Landau-Notation
Autor
Universität/Hochschule Zur Landau-Notation
stefanstiege
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.10.2020
Mitteilungen: 24
  Themenstart: 2021-08-05

Hallo! (Ich bin wahrscheinlich im falschen Unterforum, bitte einmal verschieben falls dies der Fall ist, habe nicht besseres gefunden) Ich habe eine Frage zu folgender Gleichung (die ich in der Literatur gefunden habe): \[ \sum_{i,j = 1}^{m} O(2^{i-j}) = O(m) \]. Mit welcher Begründung liegt das in der Klasse von m? Mit einem Argument, das ich mir überlegt habe, würde ich das mit der Gaußschen Summe abschätzen, hätte dann aber nur $O(m^2)$... Freundliche Grüße, Stefan


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7130
Wohnort: Milchstraße
  Beitrag No.1, eingetragen 2021-08-05

Hallo stefanstiege, \quoteon(2021-08-05 16:09 - stefanstiege im Themenstart) \[ \sum_{i,j = 1}^{m} O(2^{i-j}) = O(m) \] \quoteoff Ist damit folgendes gemeint? \[ \sum_{i= 1}^{m}\sum_{j = 1}^{m} O(2^{i-j})\] Dann sehe ich noch nicht mal, warum da \(O(m^2)\) heraus kommen sollte.


   Profil
stefanstiege
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.10.2020
Mitteilungen: 24
  Beitrag No.2, vom Themenstarter, eingetragen 2021-08-05

Hi, ja, genau das ist gemeint. Ich habe mir sozusagen überlegt (wahrscheinlich falsch), dass man $O(2^{i-j})$ durch einen jeweils konstanten Wert ($O(1)$) abschätzen kann. Und dann hätte man ja nur noch die (Gaußsche) Summe... aber hast Recht, das wäre dann vermutlich auch eher $O(m^3)$ oder so... Wie gesagt, das verwirrt mich auch etwas, dass das $O(m)$ sein soll.


   Profil
stefanstiege
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.10.2020
Mitteilungen: 24
  Beitrag No.3, vom Themenstarter, eingetragen 2021-08-05

Hi nochmal, ich sehe gerade, dass ich die Gleichung falsch im Kopf hatte, in der Literatur steht \[ \sum_{i,j=1}^m O(2^{-|i-j|}) = O(m) \] (falls das überhaupt was ändert)


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7130
Wohnort: Milchstraße
  Beitrag No.4, eingetragen 2021-08-05

\quoteon(2021-08-05 19:25 - stefanstiege in Beitrag No. 3) \[ \sum_{i,j=1}^m O(2^{-|i-j|}) = O(m) \] (falls das überhaupt was ändert) \quoteoff Das ändert einiges! Jetzt sind schon mal alle Summanden < 1. Vorher lag der größte Summand schon bei \(2^{m-1}\).


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2657
  Beitrag No.5, eingetragen 2021-08-05

Das Ganze beruht auf der Überlegung$$ \sum_{i,j=1}^m O(2^{-|i-j|}) \le O(m)\cdot\sum_{d=0}^{m-1} O(2^{-d}) \le O(m)\cdot O(1)\cdot\left(1+\frac12+\frac14+\ldots\right) = O(m) \;, $$die man allerdings etwas sorgfältiger aufschreiben müsste. --zippy


   Profil
stefanstiege
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 26.10.2020
Mitteilungen: 24
  Beitrag No.6, vom Themenstarter, eingetragen 2021-08-05

Alles klar, ich werds mir anschauen, vielen Dank!


   Profil
stefanstiege hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]