Big O del ciclo di 0 ... n con ciclo annidato che fa k iterazioni [duplicato]

Question

Big O del ciclo di 0 ... n con ciclo annidato che fa k iterazioni [duplicato]

#1 da (3 voti)

-1

I miei colleghi e io stiamo discutendo di questo codice e abbiamo bisogno di una terza parte per risolvere la nostra discussione:)

Random randNum = new Random();
int[] A = Enumerable.Repeat(0, 1000).Select(i => randNum.Next(0, 100)).ToArray();
int k = randNum.Next(0, A.Length);
int[] B = new int[A.Length - k];

for (int i = 0; i < B.Length; i++)
{
    int min = A[i];

    for (int j = i + 1; j <= i + k; j++)
    {
        min = Math.Min(A[j], min);
    }

    B[i] = min;
}

Cosa dovrebbe essere considerato nella notazione O grande?

big-o

posta David Sherret 19.01.2016 - 21:35

fonte

1 risposta

Leggi altre domande sui tag big-o

Perché fare riferimento agli array, invece di copiarli, è cattivo? [chiuso] Informazioni sul nodo che serve pagine dinamiche

score 3 · Accepted Answer

Supponiamo che tu voglia il Big-O in termini di dimensioni dell'array A (cioè n = A.Length ).

La dimensione di B è A.Length-k e k è un numero casuale compreso tra 0 e la dimensione di A.

Big-O è tutto basato sugli scenari peggiori. Lascerò un esercizio al lettore per dimostrare che il caso peggiore qui è quando k = A.Length / 2 = n / 2 . In tal caso, B.Length = A.Length - k = n / 2 .

Quindi abbiamo entrambi i cicli che eseguono n / 2 di lavoro, per una risposta finale di O (n ^ 2)