Tempo di esecuzione asintotico di for-loops

Question

Tempo di esecuzione asintotico di for-loops

#1 da (6 voti)

2

Ho questa domanda a cui ho bisogno di rispondere:

What is the asymptotic running time for the following piece of code?
if (N < 1000)
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      A[i] = j;
else
  for (int i = 0; i < N; i++)
    A[i] = i;
logarithmic in N

linear in N ()

linearithmic in N

quadratic in N

E il risultato corretto è " 2. lineare in N "che non riesco a capire perché, dal momento che per quello che ho capito, vogliamo accettare il caso peggiore > best case.

Il caso peggiore qui è che l'istruzione if è eseguita e il tempo sarebbe quindi quadratico in N. Sono consapevole che stiamo cercando di trovare un qualche tipo di media di più tentativi, ma come posso sapere qual è il valore di N è? Se N è veramente alto (10000), è ovviamente l'altra istruzione che viene eseguita la maggior parte delle volte. Ma possiamo assumere questo o ho frainteso qualcosa?

runtime algorithms big-o algorithm-analysis

posta owwyess 17.08.2014 - 16:53

fonte

1 risposta

Leggi altre domande sui tag runtime algorithms big-o algorithm-analysis

Qual è il controller in Django MVC? Impostazione dei campi con il valore predefinito corretto

score 6 · Accepted Answer

La definizione dei tempi di corsa asintotica è ... benintestata. Cioè, è il comportamento della funzione come N è molto grande. Il comportamento della funzione su N minore è irrilevante. In questo caso, poiché N è molto grande, è maggiore di 1000. Ciò significa che il codice all'interno della clausola if è in realtà completamente irrilevante per quanto riguarda il tempo di esecuzione asintotico (Nota: non sono sicuro del perché hai detto che il resto la dichiarazione è eseguita "la maggior parte" delle volte se N è veramente alto, è chiaramente eseguito "tutte" le volte in cui N è veramente alto). Tutto ciò che conta è il codice nel resto.

Nota, il "caso peggiore" a cui stai pensando è legittimo nei casi di operazioni sequenziali. Cioè, se non ci fosse il blocco if-else, ma entrambi i rami del codice sono stati semplicemente eseguiti tutto il tempo, allora quello che hai detto sarebbe esattamente corretto: se esegui un codice quadratico in N seguito da un codice che è lineare in N, il codice generale è quadratico, come hai detto tu.