3. Randomize()

Randomize()

  • D

    Lässt sich optimieren, auf reduzierte Komplexität von O(n²) zu O(n).

    Alter Code:

    for(int a=0; a<anzahl;a++)
    {
        for(int i=0;i<a;i++)
        {
            if(carray[i]==carray[a])
            {
                return false;
            }
        }
    }

    Neuer Code:

    #include <iostream>
#include <ctime>
#include <cstdlib> // rand, srand

void randomize()
{
    srand(time(0));
}

/** vergleiche die zahlen deiner liste nur bis zur neuen zahl    **/
/** ein doppelter vergleich mit den alten zahlen ist nicht nötig **/
/** es ist bekannt das diese einmalig sind!                      **/  

bool checkme(int carray[], int checkpos)
{
    for(int a=0; a < checkpos; a++)
    {
        if(carray[checkpos] == carray[a])
        {
            return false;
        }
    }
    return true;
}

int main()
{
    int x[49];
    randomize();

    for(int i=0;i<=48;i++)
    {
        do
        {
            x[i] = rand()%255;
        }
        while(checkme(x, i)==false);
    }

    for(int i=0;i<=48;i++)
      std::cout << x[i] << std::endl;
}

    Ich hoffe das sehe ich richtig.

    0
  • C
    Mod

    Wir können auch gleich O(1) daraus machen

    #include <iostream>
#include <ctime>
#include <cstdlib> // rand, srand

void randomize()
{
    srand(time(0));
}

int main()
{
    int x[49];
    bool check[255]={};
    randomize();

    for(int i=0;i<=48;i++)
    {
        do
        {
            x[i] = rand()%255;
        }
        while(check[x[i]]);
        check[x[i]]=true;
    }

    for(int i=0;i<=48;i++)
      std::cout << x[i] << std::endl;
}
    0
  • N

    Falls es mit der STL gelöst werden soll:

    #include <iostream>
#include <vector>
#include <algorithm>

int main() 
{ 
    srand(static_cast<unsigned int>(time(0))); 
	const size_t max_size = 256;
	const size_t size = 49;

	std::vector<int> numbers(max_size);
	for (int i = 0; i < max_size; ++i)
		numbers[i] = i;

	std::random_shuffle(numbers.begin(), numbers.end()); 

	for (int i = 0; i < size; ++i)
		std::cout << numbers[i] << std::endl;
}
    0
  • D

    camper schrieb:

    Wir können auch gleich O(1) daraus machen

    Nein können wir nicht!

    for(int i=0;i<=48;i++)
    {
        do
        {
            x[i] = rand()%255;
        }
        while(check[x[i]]);
        check[x[i]]=true;
    }

    das hineinziehen des Funktionsaufrufs ändert die Komplexität nicht, wenn du darüber nachdenkst kommst du vielleicht von selber darauf.

    Eine Auswahl und Vergleich von Zufallsbestimmen Zahlen kann niemals O(1) sein, w.z.B konstante Aufrufe von 102, oder 100, 48 Schleifen. Es ist nicht bekannt wie viele Aufrufe stattfinden, der Aufruf ist zwar linear aber das n in O(n) müsste für diese n-Funktion erst noch ermittelt werden. Das n in O(n) hätte also einen min-Wert mittel-Wert und einen max-Wert und kann damit nicht const sein, was die Voraussetzung für O(1) ist.

    Bem: for() ist Konstant O(1), while() O(n) --> O(n+1) = O(n)

    0
  • C
    Mod

    Ich bezog mich nur auf die Komplexität des Vergleichs. Schließlich terminiert ein solcher Algorithmus im schlimmsten Fall gar nicht.

    0
  • D

    Doch tut er, weil die Funktion rand() garantiert das ALLE zahlen gleichverteilt vorkommen und folglich der max-Wert der Funktion dem O(lim n->∞ - const) entspricht, wobei gilt n != ∞ und const fest.

    0
  • V

    Also den Vergleich kriegten wir von O(n^2) über O(n) runter auf O(1).
    Interesaant ist die Komplexität des ursprünglichen Algos, wenn man damit n zufällige Zahlen von 1 bis n finden will. Für n=10000 waren es glaub ich 20 Minuten und n=100000 hab ich mich nicht getraut. Ich glaube auch nicht, daß es O(n^3) ist, sondern was viel Schrecklicheres.

    0
  • D

    vokhard schrieb:

    Also den Vergleich kriegten wir von O(n^2) über O(n) runter auf O(1).

    Also ich weiß ja nicht wo du Informatik/Mathematik studiert hast aber es ist wirklich nicht O(1), mein letzter Kommentar dazu.

    In diesem Sinne
    Gruß Deep Copy

    0
  • L

    Doch es der Vergleich ist bei camper O(1).

    @volkard: Dann probier doch mal Nexus Algorithmus aus. Der hat ja O(n) für die Gesamtlaufzeit ;).
    Für den ursprünglichen Algorithmus müsste man die erwartete Laufzeit ausrechnen... Würd man spontan auf O(n^3 log(n)) tippen..

    0
  • V

    DeepCopy schrieb:

    vokhard schrieb:

    Also den Vergleich kriegten wir von O(n^2) über O(n) runter auf O(1).

    Also ich weiß ja nicht wo du Informatik/Mathematik studiert hast aber es ist wirklich nicht O(1), mein letzter Kommentar dazu.

    In diesem Sinne
    Gruß Deep Copy

    Der VERGLEICH, Du Nase! Du Weihnachtsmann!
    Der Aufruf von checkme(i) war vorher quadratisch und jetzt ist er ersetzt durch das konstante check[x[i]].
    Der Vergleich steckt noch in einer äußeren Schleife, weswegen der gesamte Algo O(viel) hat und nicht O(1), das ist klar.

    0
  • D

    volkhard schrieb:

    Der VERGLEICH, Du Nase! Du Weihnachtsmann!

    Ich kann mir ein Grinsen nicht verkneifen, ich ein Weihnachtsmann 👍

    Nicht böse sein, aber woher sollte ich wissen das du mit VERGLEICH eine Stelle im Code und nicht den ganzen Algo meinst.

    0
  • C
    Mod

    DeepCopy schrieb:

    ... woher sollte ich wissen das du mit VERGLEICH eine Stelle im Code und nicht den ganzen Algo meinst.

    Weil du damit angefangen hast, dich auf den Code, der den Vergleich durchführt, zu beschränken.

    DeepCopy schrieb:

    Lässt sich optimieren, auf reduzierte Komplexität von O(n²) zu O(n).

    Alter Code:

    ...
    0
Anmelden zum Antworten