Peggior complessità del caso per un algoritmo

Question

Qual è la peggiore complessità del tempo di caso t (n): - Sto leggendo questo libro sugli algoritmi e come esempio come ottenere la T (n) per .... come la selezione Algoritmo di ordinamento

---

Come se avessi a che fare con selectionSort (A [0..n-1])

//sorts a given array by selection sort
//input: An array A[0..n - 1] of orderable elements.
//output: Array A[0..n-1] sorted in ascending order

fammi scrivere uno pseudocodice

for i <----0 to n-2 do
  min<--i
for j<--i+1 to n-1 do
   ifA[j]<A[min] min <--j
swap A[i] and A[min]

-------- Lo scriverò anche in C # ---------------

private int[] a = new int[100];

// number of elements in array
private int x;

// Selection Sort Algorithm
public void sortArray()
{
  int i, j;
  int min, temp;

  for( i = 0; i < x-1; i++ )
  {
    min = i;

    for( j = i+1; j < x; j++ )
    {
      if( a[j] < a[min] )
      {
        min = j;
      }
    }

    temp = a[i];
    a[i] = a[min];
    a[min] = temp;
  }
}

==================

Ora come ottenere la t (n) o come è nota la complessità temporale peggiore

Answer 1

@ sara jons Il set di diapositive a cui hai fatto riferimento e l'algoritmo ivi

La complessità viene misurata per ogni operazione primitiva / atomica nel ciclo for

for(j=0 ; j<n ; j++)
{
    //...    
}

Le diapositive valutano questo loop come 2n + 2 per i seguenti motivi:

Il set iniziale di j = 0 (+1 op)

Il confronto di j < n (n ops)

L'incremento di j ++ (n ops)

L'ultima condizione per verificare se j < n (+1 op)

In secondo luogo, il confronto all'interno del ciclo for

if(STudID == A[j])      
    return true;

Questo è valutato come n ops. Quindi il risultato se sommi +1 op, n ops, n ops, +1 op, n ops = 3n + 2 complessità. Quindi T (n) = 3n + 2

Riconosci che T (n) non è uguale a O (n).

Answer 2

Sarebbe O (n ^ 2).

Il motivo è che hai un singolo ciclo per nidificato in un altro ciclo per. Il tempo di esecuzione per il ciclo interno per, O (n), accade per ogni iterazione del ciclo esterno per, che è di nuovo O (n). Il motivo per cui ciascuno di questi individualmente è O (n) è perché richiedono un tempo lineare dato la dimensione dell'input. Maggiore è l'input, più tempo impiegherà su una scala lineare, n.

Per elaborare la matematica, che in questo caso è banale, basta solo moltiplicare la complessità del ciclo interno per la complessità del ciclo esterno. n * n = n ^ 2. Perché ricorda, per ogni n nel ciclo esterno, devi fare di nuovo n per l'interno. Per chiarire: n volte per ogni n.

O (n * n).

O (n ^ 2)

Answer 3

A proposito, non dovresti confondere la complessità (indicata da big-O) e la funzione T. La funzione T è il numero di passaggi che l'algoritmo deve eseguire per un determinato input.

Quindi, il valore di T (n) è il numero effettivo di passaggi, mentre O (qualcosa) indica una complessità. Con l'abuso convenzionale della notazione, T (n) = O (f (n)) significa che la funzione T (n) ha al massimo la stessa complessità di un'altra funzione f (n), che di solito sarà la funzione più semplice possibile della sua classe di complessità.

Questo è utile perché ci consente di concentrarci sul quadro generale: ora possiamo facilmente confrontare due algoritmi che possono avere funzioni T (n) molto diverse osservando come eseguono " nel lungo eseguire quot &;.

Answer 4

Un altro flashback di dottorato qui.

Innanzitutto, la funzione T è semplicemente la quantità di tempo (di solito in un certo numero di passaggi , di cui più sotto) che un algoritmo impiega per eseguire un'attività. Che & Quot; step & Quot; è, è in qualche modo definito dall'uso; ad esempio, è convenzionale contare il numero di confronti negli algoritmi di ordinamento, ma il numero di elementi cercati negli algoritmi di ricerca.

Quando parliamo del momento peggiore di un algoritmo, di solito lo esprimiamo con " notazione big-O " ;. Quindi, per esempio, senti che l'ordinamento delle bolle impiega O (n & # 178;) tempo. Quando usiamo la notazione O grande, quello che stiamo veramente dicendo è che la crescita di alcune funzioni - in questo caso T - non è più veloce della crescita di alcune altre funzioni per una costante. Questo è

T (n) = O (n & # 178;)

significa per qualsiasi n , non importa quanto sia grande, c'è una costante k per la quale T (n) & # 8804; kn # 178 &; . Un punto di confusione qui è che stiamo usando il & Quot; = & Quot; segno in modo sovraccarico: non significa che i due siano uguali in senso numerico, solo che stiamo dicendo che T (n) è delimitato da kn # 178 &;.

Nell'esempio della domanda estesa, sembra che contino il numero di confronti nel ciclo for e nel test; aiuterebbe a vedere il contesto e la domanda a cui stanno rispondendo. In ogni caso, tuttavia, mostra perché ci piace la notazione big-O: W (n) qui è O (n) . (Prova: esiste una costante k, vale a dire 5, per la quale W (n) & # 8804; k (3n) +2. Segue la definizione di O (n ) ).

Se vuoi saperne di più, consulta eventuali buoni algoritmi, ad es. Introduzione agli algoritmi , di Cormen et al.

Answer 5

scrivi pseudo codici per cercare, inserire e rimuovere le informazioni sugli studenti dalla tabella hash. calcola la complessità temporale migliore e peggiore

Answer 6

3n + 2 è la risposta corretta per quanto riguarda il loop. Ad ogni passo del ciclo, vengono eseguite 3 operazioni atomiche. j ++ è in realtà due operazioni, non una. e j