Big O обозначение (п^2)

Question

Пример 1

for (int i = 0; i < n; i++) { 
    for (int j = 0; j < n; j++) { 
     System.out.println(count++); 
    } 
} 

Пример 2

for (int i = 0; i < n * n; i++) {    
    System.out.println(count++); 
} 

Оба примера дают мне большую O (N^2). но какой ans лучший?

Answer 1

Оба петель одинаковы. Нет лучшего. Но если значение N велико, тогда значение N*N будет переполняться, и вам нужно вернуться к двум для циклов. Таким образом, вы можете использовать это в соответствии со своим значением N.

Answer 2

Чтобы найти код best, было бы лучше его скомпилировать и использовать javap -c ClassName.class, чтобы просмотреть сгенерированный байт-код для обоих методов. Я использовал метод foo для первого и bar метод для последнего.

public static void foo(int n) { 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
     for (int j = 0; j < n; j++) { 
      System.out.println(count++); 
     } 
    } 
} 

public static void bar(int n) { 
    int count = 0; 
    for (int i = 0; i < n * n; i++) { 
     System.out.println(count++); 
    } 
} 

Таковы результаты:

public static void foo(int); 
    Code: 
     0: iconst_0  
     1: istore_1  
     2: iconst_0  
     3: istore_2  
     4: iload_2  
     5: iload_0  
     6: if_icmpge  38 
     9: iconst_0  
     10: istore_3  
     11: iload_3  
     12: iload_0  
     13: if_icmpge  32 
     16: getstatic  #2  // Field java/lang/System.out:Ljava/io/PrintStream; 
     19: iload_1  
     20: iinc   1, 1 
     23: invokevirtual #3  // Method java/io/PrintStream.println:(I)V 
     26: iinc   3, 1 
     29: goto   11 
     32: iinc   2, 1 
     35: goto   4 
     38: return   

public static void bar(int); 
    Code: 
     0: iconst_0  
     1: istore_1  
     2: iconst_0  
     3: istore_2  
     4: iload_2  
     5: iload_0  
     6: iload_0  
     7: imul   
     8: if_icmpge  27 
     11: getstatic  #2  // Field java/lang/System.out:Ljava/io/PrintStream; 
     14: iload_1  
     15: iinc   1, 1 
     18: invokevirtual #3  // Method java/io/PrintStream.println:(I)V 
     21: iinc   2, 1 
     24: goto   4 
     27: return   

В конце концов, последняя реализация, как представляется, лучше чем прежний из-за менее операций, сделанных.

Я не эксперт в этом, поэтому, если кто-либо может отредактировать/выполнить лучший анализ, не стесняйтесь это делать. Я написал этот ответ, поскольку он не вписывался ни в один комментарий.

Answer 3

Когда вы говорите лучше, в программном смысле есть два способа определить, с точки зрения памяти и производительности (обычно итерации).

Что касается памяти, второй вариант лучше всего, потому что используются только 2 переменных (i и n). Наряду с этим только одно назначение переменной (i ++ => i = i + 1) происходит для каждой итерации. , тогда как в первом, i ++ и j ++, две операции присваивания выполняются для каждой итерации. Поскольку переназначение переменных также занимает значительное количество времени при высоких операциях обработки, второе лучше.

С точки зрения итераций, оба они одинаковы.