Как рассчитать сложность данного кода

Question

Function(int n)
if(n<=2)
 return 1;
for(i=n ; i>n/8 ; i-=n/2)
 for(j=n ; j>2 ; j=j/2)
  syso();
return Function(n/2);

Для расчета я сделал следующее: T (n) = T (n / 2) + O (1) + 2logn

• T (n / 2): рекурсивный вызов функции.
• O (1): оператор if.
• 2logn: первый «for» будет запускаться только 2 раза * (второй «for»), который будет выполняться logn раз.

** Я предположил, что второй цикл for будет делить j на 2, что означает, что у меня будет j / 2 ^ k кратных итераций = logn.

С той же логикой следующий шаг: T (n) = (T (n / 2 ^ 2) + O (1) + 2logN) * ​​1017 * + O (1) + 2logn Продолжайте идти до шага К: T (n) = T (n / 2 ^ k) + O (1) + 2 * Клогн

С первого оператора «if» функция остановится, когда n <= 2, поэтому: <br> n / 2 ^ k =? 2> k = log (n) - 1.

Теперь я помещаю k в функцию и получаю: T (n) = T (2) + O (1) + 2 (logn) ^ 2 - 2logn Мы знаем, что T (2) = O (1), поскольку он выполняет только проверку "если".

T (n) = O (1) + 2 (logn) ^ 2 - 2logn. Предполагая, что все шаги, которые я сделал, верны, сложность O ((logn) ^ 2)?

Или я ошибся в своих расчетах.

Answer 1

Вот вывод, чтобы дополнить численный эксперимент Danielle.

---

Как отмечается в комментарии Danielle, внешний цикл выполняется только дважды, один раз с i = n и один разi = n/2.Внутренние циклы не зависят от i, что облегчает задачу.

Цикл над j будет выполняться ровно floor(log2(n)) раз, поэтому при условии, что syso() равно O(1):

т.е. ваше отношение повторения правильное, но расширение не было.

Применение условия остановки n <= 2 для поиска максимального значенияиз k:

Математические заметки:

• Число, округленное в меньшую сторону, отличается от исходного значенияменее чем на 1:

  floor(x) = x + O(1)
  

• Арифметическая серия 1 + 2 + ... + n = n*(n+1)/2.

Применение вышеуказанных пунктов:

Что соответствует тому, что указывают числовые результаты.

Answer 2

Вы можете использовать пример программы, чтобы подсчитать, сколько раз внутренний цикл вызывается для различных значений n.Запустив программу ниже, похоже, сложность ~ 2*log(n)^2.

package example;    
public class Example1 {
  public static void main(String[] args) {
    int c=4;
    for (int i=0;i<20;i++) {
      new FunctionOpsCount(c).dump();
      c=c*2;
    }
  }
}

class FunctionOpsCount {
  int ops;
  private int n_;

  FunctionOpsCount (int n) {
    this.n_=n;
    f(n);
  }

  private int f(int n) {
    if(n<=2)
      return 1;
    for(int i=n ; i>n/8 ; i-=n/2)
      for(int j=n ; j>2 ; j=j/2)
        incrementOp();
    return f(n/2);
  }
  private void incrementOp() {
    ops++;
  }
  void dump() {
    System.out.printf("n=%d ops=%d 2*log(n)^2/ops=%f%n", n_, ops, 2.*Math.log(n_)*Math.log(n_)/ops);
  }
}

и она печатает:

n=4 ops=2 2*log(n)^2/ops=1,921812
n=8 ops=6 2*log(n)^2/ops=1,441359
n=16 ops=12 2*log(n)^2/ops=1,281208
n=32 ops=20 2*log(n)^2/ops=1,201133
n=64 ops=30 2*log(n)^2/ops=1,153087
n=128 ops=42 2*log(n)^2/ops=1,121057
n=256 ops=56 2*log(n)^2/ops=1,098178
n=512 ops=72 2*log(n)^2/ops=1,081019
n=1024 ops=90 2*log(n)^2/ops=1,067673
n=2048 ops=110 2*log(n)^2/ops=1,056997
n=4096 ops=132 2*log(n)^2/ops=1,048261
n=8192 ops=156 2*log(n)^2/ops=1,040982
n=16384 ops=182 2*log(n)^2/ops=1,034822
n=32768 ops=210 2*log(n)^2/ops=1,029542
n=65536 ops=240 2*log(n)^2/ops=1,024966
n=131072 ops=272 2*log(n)^2/ops=1,020963
n=262144 ops=306 2*log(n)^2/ops=1,017430
n=524288 ops=342 2*log(n)^2/ops=1,014290
n=1048576 ops=380 2*log(n)^2/ops=1,011480
n=2097152 ops=420 2*log(n)^2/ops=1,008951