Блог

 public static void main(String[] args) {

  Scanner sc = new Scanner(System.in);

  int n = sc.nextInt();
  int m = sc.nextInt();
  int result = 0;

  for (int i=0; i < n; i  ) {
    for (int j=m; j > 0; j--)
      result  = 1;
    m -= 1;

  }
  System.out.println(result);
}
  

Вопрос является истинным или ложным вопросом. Утверждение таково: «Временная сложность следующей программы, когда n намного больше 2 m, равна O (n m)». Истина или ложь?

Временная сложность в вопросе относится к временной сложности наихудшего случая. Это то, что я сделал до сих пор:

Внутренний цикл выполняется m раз, и значение m уменьшается на 1 каждый раз. Тогда общее количество итераций внутреннего цикла равно: m m — 1 m — 2 m — 3 …. 3 2 1.

Мы можем считать это арифметической последовательностью.

Тогда общее число итераций внутреннего цикла равно: m(m 1) / 2 = (m2 m) / ².

После того, как m достигнет 0, поскольку n намного больше 2 * m, внешний цикл будет продолжать выполняться в O (1) раз в n — m раз больше.

Итак, временная сложность равна: (m ² m) / 2 n — m = O(m ²).

Правильно ли это подходить к этому вопросу?

Нет, это неверно. Прежде всего, здесь нет «наихудшего случая» или «наилучшего случая», поскольку количество шагов полностью определяется n и m .

Вопрос, как вы заявили, вопрос «да / нет». Таким образом, простое вычисление временной сложности не является правильным подходом к этому вопросу (и, кстати, результат не O(m^2) таков — вы не можете просто отбросить n !).

Ваши рассуждения до последнего шага верны. Количество шагов, как вы правильно рассчитали, (m^2 - m)/2 n (после упрощения). Вопрос в том, является ли (m^2 - m)/2 n член множества O(mn) , исходя из предположения, что n >> 2m ?

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

 (m^2 - m)/2   n < nm (eventually, as n, m grow)
  

Теперь деление nm на с обеих сторон дает эквивалентное неравенство

 (m - 1)/(2n)   1/m < 1
  

По предположению, первый член обращается в нуль, поэтому мы остаемся с 1/m < 1 тем, что явно верно по мере m роста. Следовательно, гипотеза верна, и ответ положительный.