Informatiker Board | Druckvorschau: Komplexität vom Algorithmus

Geschrieben von evinda am 27.07.2014 um 19:40:

Komplexität vom Algorithmus

Hallo!!! Wink

Ich will die Komplexität vom folgenden Algorithmus finden.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:

 Merge(A,p,q,r)
           n1=q-p+1;
           n2=r-q;
           for i<-1 to n1
               L[i]<-A[p+i-1]
           for j<-1 to n2
                R[j]<-A[q+j]
           L[n1+1]<-oo  ,   R[n2+1]<-oo   
               
           
           i<-1, j<-1
           for k<-p to r
              if L[i]<=R[j] then
                  A[k]<-L[i]
                  i<-i+1
              else
                  A[k]<-R[j]
                  j<-j+1
             
      
        MERGESORT(A,p,r)
           if p<r then
              q<-floor((p+r)/2)
              MERGESORT(A,p,q)
              MERGESORT(A,q+1,r)
              Merge(A,p,q,r)

In meinen Buch,steht das die Komplexität die folgende ist:

$[latex] T(n)=\begin{cases}<br /> c & ,n=1\\ <br /> 2T(n/2)+cn & ,n>1<br /> <br /> \end{cases}[/latex]$

ich habe aber nicht verstanden,wie man zu diesen Ergebnis kommt.
Könntet ihr mir weiterhelfen? geschockt

Geschrieben von ed209 am 06.08.2014 um 23:58:

RE: Komplexität vom Algorithmus

Für mich sieht das eher nach einem Zwischenschritt aus. In welcher Form suchst du das ergebnis?

Kannst Du mit eigenen Worten wiedergeben was die Lösung im Buch bedeutet?