zeitkomplexität

[delphi_newbie_123]

Hi,
ich habe eine tabelle

Delphi-Quellcode:

n            10000   20000   30000     100000

Sekunden       2       7       27        67

wie komme ich mit Hilfe dieser Werte auf die Zeitkomplexität des Algorithmus ?
Habe momentan einen kompletten Blackout wär echt nett wenn jemand helfen könnte :/

es sollte O(~n*3wurzel aus n rauskommen)

[Grishnak]

Ich kenne mich zwar nicht mit der Zeitkomplexität von Algorithmen aus, aber mir ist an deiner Tabelle folgendes aufgefallen:

Bei einer Verdoppelung von n (von 10.000 auf 20.000) benötigt der A. 3,5 mal soviel Zeit (von 2 auf 7) - entspricht Faktor 1,75 (3,5 / 2).
Bei einer Verdreifachung von n (auf 30.000) benötigt der A. 13,5 mal soviel Zeit (von 2 auf 27) - entspricht Faktor 4,5 (13,5 / 3).
Bei einer Verzehnfachung von n (auf 100.000) benötigt der A. 33,5 mal soviel Zeit (von 2 auf 67) - entspricht Faktor 3,35 (33,5 / 10).

Kann es sein, dass die Zeitdauer für n=100.000 falsch ist? Wenn nicht, würde der A. irgendwann zwischen n=30.000 und n=100.000 plötzlich wieder schneller werden!?

[Jelly]

Zitat:

Zitat von delphi_newbie_123

wie komme ich mit Hilfe dieser Werte auf die Zeitkomplexität des Algorithmus ?
...
es sollte O(~n*3wurzel aus n rauskommen)

Hau dir die Werte in Excel rein und lass dir durch einen Polynomfit 3-ten Grades die Gleichung ausreichnen.

[alzaimar]

Was ist den das für ein Algorithmus? Zeig den mal. Komplexität wird nicht empirisch geraten sondern per Analyse des Algorithmus berechnet.

[Der_Unwissende]

Hi,
ich glaube du kannst die Zeitkomplexität deines Algorithmus nur sehr schlecht durch das aufstellen einer Tabelle lösen. Dein größtes Problem dürfte es schon sein richtig abzuschätzen ob es sich um ein O, Theta oder Omega handelt.
Und da in Assymptotischen Laufzeiten teilweise recht große Konstanten versteckt sind, hm, dürfte schwer sein.
Desweiteren wirst du auch nur schwer abschätzen können, wieviel Zeit genau für andere Prozesse verwendet werden (wenn z.B. bei sehr großen n Windows auch anderen Prozessen Rechenzeit gibt) und dann wäre da auch noch caching (wenn bei sehr großen n sehr häufig das gleiche getan wird). Sind deine n groß genug kommen eh sehr Unterschiedliche Speicherzugriffe hinzu.
Da wird es leider wenig nutzen, dass du das Programm immer auf den letzten Rechner laufen lässt.

Also genau aus all den Gründen abstrahiert man ja eigentlich von der konkreten Zeit und betrachtet das assymptotische Laufzeitverhalten.

Hm, ob man aus der konkreten Zeit zurückrechnen kann weiß ich gerade gar nicht, muss ich mir mal näher anschauen.

[delphi_newbie_123]

Delphi-Quellcode:

#!/usr/bin/tclsh
#!/usr/bin/env tclsh

puts ""
puts "Ich berechne alle Primzahlen im Bereich 'Null bis zu einer eingegeben natürlichen Zahl'."
puts ""
puts "Bitte die Zahl eingeben:"
set zahl [gets stdin]

set primzahl_liste {}

#set anfang [clock seconds]

for {set i 2} {$i<=$zahl} {incr i} {
   set prim 1
   set test [expr sqrt($i)]
   foreach primzahl $primzahl_liste {
      if {$primzahl>$test} then {
         break
      } else {
         if { [expr $i%$primzahl]==0 } then {
            set prim 0
            break
         }
      }
   }
   if {$prim==1} then {
      lappend primzahl_liste $i
   }
}

#set ende [clock seconds]

puts ""
#puts "Im Zahlbereich bis $zahl gibt es [llength $primzahl_liste] Primzahlen:"
#puts $primzahl_liste
puts "Im Zahlbereich bis $zahl gibt es [llength $primzahl_liste] Primzahlen:"

#puts "Benötigte Zeit: [expr $ende - $anfang] Sekunden"