Вычислить время выполнения функции

Question

Вычислить время выполнения в Θ (·) как функцию от N.

public static void p5(int N) {
  for (int i = 1; i <= N * N; i *= 2) { 
     for (int j = 0; j < i; j++) { 
          System.out.println("moo"); 
     } 
  } 
 }

Для этого я начал вычислять время выполнения для нескольких значений N.

N = 1 C (N) = 1, поскольку j = только 0

N = 2 C (N) = 7, поскольку j = 0 для i = 1, j = 0,1 для i =2, j = 0,1,2,3 для i = 4

N = 3 C (N) = 15, поскольку j = 0 для i = 1, j = 0,1 для i = 2, j= 0,1,2,3 для i = 4, j = 0,1,2,3,4,5,6,7 для i = 8

Итак, существует закономерность:

C (1) = 1 = 2 ^ 0

C (2) = 7 = 2 ^ 0 + 2 ^ 1 + 2 ^ 2

C (3) = 15 =2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3

C (4) = 31 = 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 + 2 ^ 4

C (N) = 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 + 2 ^ 4 +… + 2 ^ N = 2 ^ (N + 1) - 1

ИтакЯ получаю Θ (2 ^ N) в качестве ответа!Тем не менее, ответ N ^ 2.

Можете ли вы помочь мне понять, в чем проблема?

Answer 1

Сложность p5 на самом деле O(n^2), вы можете вычислить ее формально;или просто отредактируйте метод так, чтобы он возвращал количество выполненных циклов;и вычислите соотношение ops/(N^2), чтобы доказать это.Код ниже выводит вывод:

p5 N=1 took op=1 operations, ratio=1,000000
p5 N=2 took op=7 operations, ratio=1,750000
p5 N=4 took op=31 operations, ratio=1,937500
p5 N=8 took op=127 operations, ratio=1,984375
p5 N=16 took op=511 operations, ratio=1,996094
p5 N=32 took op=2047 operations, ratio=1,999023
#etc..

и код:

package sample;
public class SampleComplexity {
  public static int p5(int N) {
    int res = 0;
    for (int i = 1; i <= N * N; i *= 2) {
      for (int j = 0; j < i; j++) {
        //count operations here
        res++;
      }
    }
    return res;
  }

  public static void main(String[] args) {
    int N=1;
    for (int i=0;i<10;i++) {
      int p5 = p5(N);
      System.out.printf("p5 N=%d took op=%d operations, ratio=%f%n", N, p5, 1.*p5/N/N);
      N=N*2;
    }
  }
}

Answer 2

Ваша ошибка, например, здесь:

C (4) = 31 = 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 + 2 ^ 4

Если выпоставьте 4 в своей функции, у вас есть 2, что не равно вычисленному вами значению.