Zeitkomplexität

[Daniel3324]

Hallo Leute!

Sitze vor einer Aufgabe die mir ein wenig Probleme bereitet :-( ich muss einen Algorithmus programmieren der die gemeinsamen Zahlen in beiden Reihungen sortiert ausgibt. Es sind zwei Reihungen (arrays) der Länge n > 0 gegeben. Ausserdem soll der Algorithmus eine Zeitkomplexität von O(n log n) haben.

public class ShellSort {
public static void main (String args []) {
try {
if (sort(args) != null && args.length > 0) // sortiere argumente
for (int n = 0; n < args.length; ++ n)
System.out.println(args[n]);

[\code]
das war mein Ansatz bin leider nicht zufrieden und komme nicht weiter mit meinem Ansatz, bitte deswegen um kleine Hilfe.

Gruß
Daniel

 

[Timmah]

Tja,

also n*log(n) hat z.B. der Quicksort oder Mergesort.

Im ersten Schritt solltest du einfach das erste Array nehmen, darüber mit einer for-Schleife gehen, und dabei jedes Element des Arrays1 im Array2 suchen. Wenn du es dort findest, speicherst du es einfach in einem neuen Array oder einer anderen Datenstruktur.
Dann jagst du über dieses neue Array den Quicksort und dann bist du mit der Aufgabe fertig


Also so in etwa:

//Deine beiden Arrays
int [] array1;
int [] array2;
Vector neu = new Vector();
for(int i=0; i<array1.length;i++)
{

          for(int j=0; j<array2.length;j++)
          {
                    if(array1[i] == array2[j])
                    {
                              neu.addElement(new Integer(array1[i])); 
                    }      
          }

}

int [] finalArr = new int[neu.size()];

for(int i=0; i<neu.size();i++)
{
          finalArr[i] = Integer.parseInt(neu.get(i).toString());
}

Arrays.sort(finalArr);

Der Algo von Array.sort() ist glaub ich ein Mergesort, und hat n*log(n).
Wenn du den natürlich selber programmieren musst, such dir bei google ein Struktogramm vom Mergesort oder Quicksort, und schreib den selber.

 

[Daniel3324]

Super! Vielen Dank du hast ein Bierchen bei mir gut! ;-)

Gruß
Daniel

 

[Timmah]

Super! Vielen Dank du hast ein Bierchen bei mir gut! ;-)

Gruß
Daniel

Das merke ich mir, ich komme drauf zurück

 

[Daniel3456]

Der Algorithmus macht das was er soll aber in einer höheren Zeitkomplexität!
Du gehst zwei verschachtelte Schleifen durch n * n -> O(n^2). Dann
sortierst du: Arrays.sort hat das heißt, dass der erste Teil eine zu hohe Zeitkomplexität
hat! Es bietet sich wahrscheinlich an, erst Sortierungen durchzuführen
und dann gemeinsame Elemente zu suchen. Aber wie? Ne Idee?

Gruß
Daniel

 

[Timmah]

Es geht doch um die Zeitkomplexität des Sortierens?!
Die 2 Schleifen haben mit dem Sortieren doch nichts zu tun...

 

[Timmah]

Richitg Timmah!

Aber die Zeitkomplexität ist flasch und das ist eben das enscheidene. Ich muss erst Sortierungen durchzuführen
und dann gemeinsame Elemente zu suchen. Und das machen wir nicht mit unserem code Timmah.

Gruß
Daniel

Die Komplexität bezieht sich, meiner Meinung nach, nur auf den Sortieralgorithmus. Das andere sind nur Vorbereitungen.

Aber evtl. kannst du hiermit was anfangen, habe ich eben mal zusammengeschrieben.

		int[] array1 =
		{ 3, 1, 2, 4, 2, 2, 4, 7, 9 };
		int[] array2 =
		{ 2, 2, 1, 1, 6, 7, 8, 4, 3, 6 };
		int sizeBeide = array1.length + array2.length;
		int[] arrayBeide = new int[sizeBeide];

		// Werte kopieren
		for (int i = 0; i < array1.length; i++)
		{
			arrayBeide[i] = array1[i];
		}
		int j = array1.length - 1;
		for (int i = 0; i < array2.length; i++)
		{
			arrayBeide[j] = array2[i];
			j++;
		}

		// Sortieren
		Arrays.sort(arrayBeide);

		HashMap hash = new HashMap();
		// Doppelte Ausgeben
		for (int i = 1; i < arrayBeide.length; i++)
		{
			// Wenn die HashMap den Key noch nicht hat und die Zahlen identisch sind
			if (!hash.containsKey(new Integer(arrayBeide[i])) && arrayBeide[i] == arrayBeide[i - 1])
			{
				hash.put(new Integer(arrayBeide[i]), new Integer(arrayBeide[i]));
				System.out.print(arrayBeide[i] + " ");
			}
		}

Prinzipiell ist das aber nicht ganz richtig, da der Code nur jede Zahl 1x ausgibt, doch unabhängig davon, woher die Zahl ursprünglich mal kam, aus array1 oder array2. Solange in jedem Array jede Zahl nur 1x vorkommt, funktioniert es

 

[Daniel22]

Hi Timmah!

Dieser Algorithmus sieht schon besser aus. Ich muss noch ne kleine main reinhauen und die zeit mal in ms messen. Aber jetzt schon mal danke für deine Hilfe. Du hast mir echt weitergeheufen.

Gruß
Daniel