Komplexität eines Algorithmus

Status
Nicht offen für weitere Antworten.

Unkownsyntax

Bekanntes Mitglied
Hallo hab da ein Problem und wollte sicher gehn ob es so stimmt wie ich mir das denke:

Und zwar es geht um diesesn Algorithmus:

Java:
alg(in int n) { 
 int a=... // Konstante (unabhängig von n) 
 int i=2 
 while (i <= a) { 
  int j=1 
  while (j <= n) { 
   for (k = 1..j) { 
    write(↓k) 
   } 
   j = j*2; 
  } 
  i = i*2; 
 } 
}

Und ich soll hier die asymptotische Laufzeitkomplexität in Abhängigkeit von n herausfinden.

Also ich dachte die ist n*log(n)^2 da die zwei while schleifen halbiert werden immer also logn und die for schleife linear ausgeführt wird oder?

lg daniel
 
Zuletzt bearbeitet von einem Moderator:
S

SlaterB

Gast
Java-Tags?!

a ist konstant, a führt dazu, dass die innere while-Schleife 10x oder 1000x mal oder 10^99x ausgeführt wird,
aber das ist für jedes a letztlich ein konstanter Faktor, also zu ignorieren,
bleib ein log(n),

nun ist es aber so, dass nicht für jeden der log(n)-while-Fälle genau n Aktionen ausgeführt werden,
sondern auch 1, 2, 4, 8 .. n,
das scheint mir weniger als n, n, n, n .. n,
vielleicht ergeben die innere while + for zusammen log(n)^2 oder sonst eine greifbare Formel,
kann mir das grad nicht gut vorstellen,

du könntest auf jeden Fall noch einen Testdurchlauf machen, wieviele Aktionen kommen für n=1000, 10.000, 100.000 usw raus
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
X Programmieren eines Spieles Softwareentwicklung 25
J Programmierung eines MazeGames Softwareentwicklung 1
G Anzahl der Rekursionsaufrufe eines DFS Algorithmus Softwareentwicklung 16
F Planung und Durchführung eines Projektes Softwareentwicklung 2
A Händische Programmierung eines 1:n-ORM Softwareentwicklung 3
? Fragen zur richtigen Umsetzung eines Projektes Softwareentwicklung 3
M Ada95 - Breite eines Baumes bestimmen Softwareentwicklung 3
B Konstruktion eines Epsilon Automaten & NFA Softwareentwicklung 2
B Signatur eines Abstrakten Datentyps Softwareentwicklung 10
S Länge eines char[][] Softwareentwicklung 12
F Aufwändes eines Software Projektes Softwareentwicklung 21
M Technische Abwicklung eines Onlinekaufs Softwareentwicklung 7
-horn- "Laufzeitberechnung" eines Programmes? Softwareentwicklung 5
Z Herangehensweise zum "entschlüsseln" eines Dateifo Softwareentwicklung 2
G Modellierung eines graphentheoretischen Problems Softwareentwicklung 5
V alle abgeleiten Klassen eines Interfaces finden? Softwareentwicklung 2
I Object mit Hilfe eines Class-Objectes instanzieren Softwareentwicklung 3
M Elemente eines Vektors zufällig anordnen Softwareentwicklung 2
M Software zur Erstellung eines Pflichtenhefts? Softwareentwicklung 15
F Zellen eines Excel-Sheets per VBA disablen (ausgrauen)? Softwareentwicklung 10
H Synchronisation eines Bitstreams Softwareentwicklung 4
B Programmierung eines 8051-Assemblers unter Java Softwareentwicklung 3
F Ist der Name eines Ojekts eine Eigenschaft Softwareentwicklung 7
R Algorithmus Softwareentwicklung 1
S Algorithmus für perfekte Kombination Softwareentwicklung 2
J Gibt es eine Algorithmus dafür??? Softwareentwicklung 5
U tichy algorithmus Softwareentwicklung 2
D Algorithmus um Wiederholungen zu finden Softwareentwicklung 5
S Algorithmus zur Planung der Nachprüfungen Softwareentwicklung 10
G Gewichtung auswerten? [Algorithmus auswerten] Softwareentwicklung 3
Z Algorithmus (Routenberechnung) Softwareentwicklung 18
K Knapsack Problem: Algorithmus? Softwareentwicklung 7
T Sudoku Algorithmus Softwareentwicklung 12
M [Algorithmus] Matrix nach Untermatrix durchsuchen Softwareentwicklung 15

Ähnliche Java Themen


Oben