Capisco come ottenere un'immagine generale della grande O di un ciclo annidato, ma quali sarebbero le operazioni per ogni ciclo in un ciclo annidato per?
Se abbiamo:
for(int i=0; i<n; i++)
{
for(int j=i+1; j<1000; j++)
{
do something of constant time;
}
}
In che modo esattamente otterremmo T (N)? Il ciclo esterno sarebbe n, l'interno sarebbe 1000 (n-1) e l'interno sarebbe semplicemente c è giusto?
Quindi T(n)=cn(1000(n-1)) è giusto?
Il limite come n si avvicina all'infinito rivela il grande O (n). Il ciclo interno viene eseguito solo per i primi 999 n. Per n > 999 il ciclo interno non viene eseguito e le istruzioni diventano costanti.
Come scrivere tutto questo come una funzione T (n)? Di questo non ne sono certo.
È O (1), non lineare, perché il ciclo interno verrà eseguito solo quando n è inferiore a 1000, quindi per il grande n (es: 1,001 e 100.000.000) sarà lo stesso. Come hai detto tu, potrebbe essere lineare fino al 1000, ma dopo è costante ...
Leggi altre domande sui tag algorithms big-o algorithm-analysis