Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Laufzeit T(n) (O-Notation)
Autor
Universität/Hochschule J Laufzeit T(n) (O-Notation)
s-amalgh
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 16.12.2020
Mitteilungen: 374
  Themenstart: 2022-03-22

Hallo zusammen, Ich habe eine Prüfung in einpaar Tage und ich versuche jetzt die Altklausuren zu lösen. Ich habe eine Aufgabe gelöst aber ich bin mir nicht sicher, ob meine Lösung richtig ist. die Aufgabe: In einem flachen Landstrich stehen n Sendemasten M_1, M_2,...,M_n gleicher Bauart. Bei einer Abstrahlungsleistung von w Watt hat das Signal jedes dieser Sendemasten eine maximale Reichweite von 5pw Metern. Alle Masten sollen mit derselben Abstrahlungsleistung betrieben werden. Jeder Punkt des Landstrichs soll aber nur von höchstens einem der Masten aus erreicht werden. Wie kann man möglichst effizient eine scharfe obere Schranke für die unter diesen Bedingungen maximal verwendbare Abstrahlungsleistung berechnen? Welche Laufzeit T(n) ergibt sich für Ihren Algorithmus (O-Notation)? Achtung: Hier ist nicht gefragt, dass jeder Punkt des Landes von einem Mast überdeckt wird. Stattdessen ist gefordert, dass sich die Sendebereiche nicht überlappen. Dies muss durch Begrenzung der Sendeleistung erreicht werden. meine Lösung: Idealerweise müssen die Sendmasten so gesetzt werden, dass die 5w^(1/2) voneinander entfernt sein, es gibt n Stück, also setzen wir in jeder Reihe n^(1/2) in n^(1/2) Reihen, so wird eine Fäche von [ 5w^(1/2) * n^(1/2) ] * [ 5*w^(1/2) * n^(1/2) ] abgedekt. Algorithmus liegt in O(n) richtig oder falsch? Danke im Voraus für die Antwort! :)


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3629
  Beitrag No.1, eingetragen 2022-03-22

Hallo, also ich verstehe die Aufgabe so, dass die Masten bereits an fest vorgegebenen Standpunkten stehen und nur noch herausgefunden werden soll, mit welcher maximalen Leistung man sie betreiben kann ohne eine Überlappung zu erzeugen. Gesucht ist also ein Algorithmus um aus den Standorten den kleinsten Abstand zweier Masten zu finden.


   Profil
s-amalgh
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 16.12.2020
Mitteilungen: 374
  Beitrag No.2, vom Themenstarter, eingetragen 2022-03-22

\quoteon(2022-03-22 14:08 - Nuramon in Beitrag No. 1) Hallo, also ich verstehe die Aufgabe so, dass die Masten bereits an fest vorgegebenen Standpunkten stehen und nur noch herausgefunden werden soll, mit welcher maximalen Leistung man sie betreiben kann ohne eine Überlappung zu erzeugen. Gesucht ist also ein Algorithmus um aus den Standorten den kleinsten Abstand zweier Masten zu finden. \quoteoff Danke erstmal für deine Antwort Also meinst du dass meine Lösung falsch ist? 🤔


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3629
  Beitrag No.3, eingetragen 2022-03-22

Deine Lösung hat meiner Meinung nach nichts mit der Aufgabenstellung zu tun.


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 7009
Wohnort: Niedersachsen
  Beitrag No.4, eingetragen 2022-03-25

Ich würde es auch so wie Nuramon verstehen. Gegeben sind n Masten mit ihren Positionen. Gesucht ist der kleinste Abstand zwischen zwei dieser Masten. Naive Lösung: Berechne alle paarweisen Abstände und wähle das Minimum davon. Aufwand $O(n^2)$. Interessante Frage, ob das schneller geht. Vielleicht habt ihr dazu ja etwas kennengelernt.


   Profil
s-amalgh hat die Antworten auf ihre/seine Frage gesehen.
s-amalgh hat selbst das Ok-Häkchen gesetzt.
s-amalgh wird per Mail über neue Antworten informiert.

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-2022 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]