Big O Notazione di un esempio

Il tuo argomento è completamente sbagliato in un modo interessante.

Il tempo impiegato è proporzionale a N. L'input è N. Ma qual è la dimensione di N? Per un intero a 32 bit la dimensione è 32 bit. Per un intero a 64 bit la dimensione è 64 bit. Per un bit intero ak con una dimensione di k bit, il valore N può essere grande come 2 ^ k (quasi), quindi il tempo non è O (1) nella dimensione dell'ingresso, ma O (2 ^ k) se l'input ha una dimensione di k bit.

Hai due cose da fare qui - Hai un ciclo (l'istruzione for ) e hai l'istruzione interna del ciclo ( System.out.print(i); ).

for (int i=1; i<=N; i=i+1) { 
    System.out.print(i); 
}

Vuoi iniziare dall'interno e allenarti. Per questo, System.out.print(i); è considerato O (1) - stai facendo una quantità fissa di lavoro.

for (int i=1; i<=N; i=i+1) { 
    System.out.print(i); //<-- O(1)
}

Quindi guardiamo il ciclo - questo esegue N volte, rendendolo O (N). Quindi moltiplichi questa volta l'istruzione interiore, dandoti O (1) * O (N) - che è O (N).

for (int i=1; i<=N; i=i+1) { //<-- O(N)
    System.out.print(i); //<-- O(1)
}

La cosa da ricordare qui è che il tuo input è N , non i . Puoi fare 3 cose all'interno del tuo ciclo, ma dal momento che sono tutte a costo fisso, le consideri comunque O (1)

for (int i=1; i<=N; i=i+1) { // <-- this is still O(N)
    int g = i * i;       //
    int g /= 2;          // <-- This is all still considered O(1) because N isn't involved.
    System.out.print(g); //
}