Komplexität Algorithmus

wx++ schrieb:

Wir einigen uns auf eine schlechte Aufgabenstellung, ok?

Würde ich auch sagen. Nachdem D die richtige Lösung sein soll, wäre es nett wenn wir irgendwann erfahren wie der Aufgabensteller argumentiert. Kann mir nicht vorstellen, dass da was Vernünftiges dabei herauskommt.

blurry333

Noch eine Frage .

C_n=max(1+C_n-1,1+C_n-2)
=1+max(C_n-1,C_n-2)
=1+C_n-1

Ich frag mich gerade was diese max Funktion soll ?

volkard

blurry333 schrieb:

Ich frag mich gerade was diese max Funktion soll ?

vielleicht ist es die std::max?

JaykopX

Die funktion scheint dir das Maximum der beiden übergebenen Paramter zurückzugeben. Wobei mir das rausziehen der 1 aus der Max-funktion komplizierter aussieht als einfach direkt auszuwerten...
a := C_n

Ausführlich:
C_n = max(1+C_n-1,1+C_n-2) //Anfangsterm
a = max(1+a-1,1+a-2) //Substituiert C_n = a
a = max(a+1-1,a+1-2) //Sortiert
a = max(a+0, a-1) //Größeren der beiden Terme finden mit max
a = a //Aussagen sind äquivalent
C_n = C_n //Rücksubstitution a = C_n

@JaykopX
http://de.wikipedia.org/wiki/Schildb%C3%BCrger

@blurry333
Wie wäre es, wenn du, statt die Fragen einfach so einsilbig hinzuschnmieren, mal den Kontext erklärst, damit die hilfbereiten Poster hier wissen um was es geht und sich nicht so verzetteln müssen wie oben.

Hi,

wenn bei den Sortierverfahren von log die Rede ist , meint man
doch immer den zur Basis 2 ??

http://de.wikipedia.org/wiki/Sortierverfahren

Hank Chinanski

Guck Dir mal an wie die O-Notation funktioniert, dann erledigt sich Deine Frage von selbst

Ah die Basis des Logarithmus ist egal. Hängt wohl damit zusammen dass
es immer ein konstanter Vorfaktor ist, um den sich die Logarithmen unterscheiden. Mehr weiß ich allerdings auch nicht.

JaykopX

@HurgaHurga
sorry

lieg ich falsch oder wie soll ich das verstehn

Was mich auch noch intressiert. Beim Bubble Sort soll der best case O(n) sein.
Aber ich kenn keinen Algorithmus der bei der vorsortierten Liste dies
erkennt und dann abbricht.

JaykopX schrieb:

@HurgaHurga
sorry
->http://de.wikipedia.org/wiki/Asperger-Syndrom

Ich mache dir keinen Vorwurf, dass du nicht im Geringsten verstanden hast, was blurry333 mit der Frage meint, denn er vergisst den Zusammenhang zu erwähnen und die Notation ist auch nicht hilfreich.

Wenn du allerdings aus einem einfachen 3-Zeiler durch seltsame Substitutionsmechanismen einen 6-Zeiler mit Nonsens-Ergebnis machst musst du dir schon etwas Kritik gefallen lassen. Und ein Link auf die Schildbürger schien mir nicht so hart wie das eigentlich angebrachte Dieter Nuhr Zitat.

otze

klar, bubble sort geht einmal durch. ist die liste sortiert, wird auf dem Weg keine Vertauschung mehr durchgeführt und damit kann sofort abgebrochen werden.

Hier mal eine Implementierung aus dem Internet.

Die innere Schleife wird doch auch durchlaufen wenn das Array sortiert ist.

void bubbleSort(int *array,int length)//Bubble sort function 
{
	int i,j;
	for(i=0;i<10;i++)
	{
	   for(j=0;j<i;j++)
	    {
	      if(array[i]>array[j])
		{
		   int temp=array[i]; //swap 
		   array[i]=array[j];
		   array[j]=temp;
		}

	    }

	}

}

dir fehlt die flag ob eine vertauschung statt gefunden hat

prozedur bubbleSort( A : Liste sortierbarer Elemente ) 
  n := Länge( A )
  wiederhole
    vertauscht := falsch
    für jedes i von 1 bis n - 1 wiederhole 
      falls A[ i ] > A[ i + 1 ] dann
        vertausche( A[ i ], A[ i + 1 ] )
        vertauscht := wahr
      ende falls
    ende für
    n := n - 1
  solange vertauscht und n >= 1
prozedur ende

lg lolo

Ah danke. Aber in der klassischen Variante war der best und worst case
immer O(n^2). Mit Flag ist er schneller als Quicksort

blurry625 schrieb:

Ah danke. Aber in der klassischen Variante war der best und worst case
immer O(n^2). Mit Flag ist er schneller als Quicksort

Aber doch auch nur im Best Case oder?

ja wenn es gut sortiert ist