Нахождение времени выполнения следующего кода - PullRequest
Новая
       3

Нахождение времени выполнения следующего кода

1 голос
/ 06 марта 2020 
public static int loop(int n){
  int j = 1;
  int n2 = n;
  for (int i = 0; i < n; i++) {
    n2 *= 5.0/7.0;
      for (int k = 0; k < n2; k++) {
        System.out.println("Hello.");
      }
    }
  return j;
}

Привет всем, у меня возникли трудности с определением временной сложности приведенного выше кода.

Вот что у меня есть:

Когда i = 0, выполняется внутренняя l oop: (5/7) * n

Когда i = 1, внутренний l oop выполняется: (5/7) ^ 2 * n

...

Когда i = n, внутренний l oop выполняется: (5/7) ^ (n + 1) * n

Суммируя их, я получаю O (n * (5/7) ^ n). Это точный анализ?

1 Ответ

1 голос
/ 06 марта 2020

Ваш вывод не верен; на самом деле, когда 0 n сходится к 0 при стремлении n к бесконечности, так что это определенно не верхняя граница времени выполнения алгоритма, который выполняет более 0 вещей .

В вашем алгоритме r = 5/7, но для удобства чтения я буду продолжать писать r в этом ответе. Формула для суммирования этих членов дает результат, подобный n * r * (r n + 1 - 1) / (r - 1). Дополнительный фактор r заключается в том, что последовательность не начинается с 1 * n. Нам нужно осторожно упростить эту формулу, потому что для 0 отрицательны , а доминирующий член в числителе равен 1, который доминирует r n + 1 , поскольку последнее сходится к 0, когда n стремится к бесконечности.

Если переписать его как n * r * (1 - r n + 1 ) / (1 - г) тогда это понятнее. Отбрасывая постоянные множители r и 1 / (1-r), получаем O (n * (1 - r n + 1 )), а затем отбрасываем доминирующий член -r n + 1 мы получаем O (n * 1) или просто O (n).

Другой способ увидеть это состоит в том, что последовательность ограничена сверху n * (r + r 2 + r 3 + ...), где бесконечный ряд сходится к постоянной r / (1 - r), поэтому он ограничен сверху n-кратной константой.

...