[JAVA] Complessità

[Alfredo_88]

Ho un problema con questo algoritmo di cui dovrei calcolare la complessità asintotica. Non so se sono nella sezione giusta ma il codice è scritto in java.
Come procedo per calcolare la complessità?

 public static void esercizio(int[][] a){ 
               int n=a.length; 
               int i=0; 
               int j=0; 
 
               while(i<n && j<n){ 
                    for(int k=i-1;k<=i+1;k++) 
                         for(int h=j-1;h<=j+1;h++) 
                              if(k>=0 && k<n && h>=0 && h<n) 
                                   a[k][h]++; 
                    i++; 
                    j++; 
               } 
     }

[zipangulu]

Devi cercare di dare una stima asintotica del "costo" di questo algoritmo..devi in pratica fare una stima sul numero , ripeto in modo asintotico , delle ripetizioni delle istruzioni (quindi stai attento ai vari cicli ecc)..
Comunque , premettendo che sono piuttosto arruginito a riguardo , se non sbaglio dovrebbe essere un O(n) ..c'ho preso?

[MItaly]

i e j sono sempre uguali, quindi possiamo eliminare j rimpiazzandola con i; a questo punto, il while più esterno si può trasformare in un for, ottenendo:

public static void esercizio(int[][] a)
{
    int n=a.length;

    for(int i=0; i<n; i++) // <= n iterazioni
        for(int k=i-1; k<=i+1; k++) // <= 3 iterazioni
            for(int h=i-1; h<=i+1; h++) // <= 3 iterazioni
                if(k>=0 && k<n && h>=0 && h<n)
                    a[k][h]++;
}

Come da commenti, il ciclo più esterno viene eseguito n volte, e ciascuno dei due cicli interni viene eseguito 3 volte (da i-1 a i+1 inclusi); l'if governa una singola istruzione (e non un ciclo), per cui non conta nel calcolo della complessità asintotica (darebbe come contributo una costante k, che sparisce nella notazione dell'O-grande).
Per questo, il codice più interno viene eseguito 3*3*n*k volte, ovvero la procedura è O(n) (tutte le costanti spariscono).

[Alfredo_88]

Ok! Più chiaro di così si muore! In pratica ogni volta devo determinare quante volte si itera un ciclo e determinare la complessità delle operazioni al suo interno?
Cioè se per esempio avessi questo codice:

 public static void esercizio(int[] a, int[] b){ 
          int n=a.length; 
          int m=b.length; 
 
          int i=0; 
          int j=0; 
 
          while(j<m){ 
               System.out.println(""+a[i]*b[j]); 
               j=j+((i+1)/n); 
               i=(i+1)%n; 
 
          } 
     }

i varia tra 0 e n-1 e j incrementa di 1 ogni n-1 iterazioni, fino a che rimane minore di m. Posso concludere che la complessità è n*m? (o (n-1)*(m-1) ?)