Блог

Главная - Вопросы по программированию - Нужна помощь в понимании ответа на сложность Big-O для этого кода

Нужна помощь в понимании ответа на сложность Big-O для этого кода

#c #time-complexity

Вопрос:

В соответствии с ключом ответа, ответ будет O(N). У меня не было достаточно времени, чтобы рассмотреть его внимательно. Я думал, что это i , а не i/=2 в первом цикле, поэтому я написал O(N^2). Но сейчас я не уверен, что это правильно. Я думаю, что это должно быть O(log n * log n).

Код:

 int count = 0;
for (int i = N; i > 0; i /=2)
    for (int j = 0; j < i; j  )
        count  ;

Изображение:

введите описание изображения здесь

Комментарии:

1. Да, мне очень жаль. Я загрузил не ту картинку раньше. Сейчас он обновлен, @Yunnosch

2. Внешний цикл-o(logn), внутренний-o(n) , следовательно, у нас есть o(nlogn), если я не ошибаюсь

3. @vpa1977, логика сложности не так проста. Это O(N) по причинам r3mainder вашего ответа.

4. Следовательно, я ошибаюсь -)

5. Это зависит от того, что N есть. Если это константа, вы можете выбросить «большое О» в окно, потому что циклы будут оптимизированы, и изучение того, какое «большое О» у них было бы, если бы их не было, не очень полезное знание. Лучше понять, как на самом деле работают программы, компиляторы и компьютеры.

Ответ №1:

  • На первой итерации внешнего цикла внутренний цикл выполняется N раз
  • На второй итерации внутренний цикл выполняется N/2 раза
  • На каждой последующей итерации внутренний цикл выполняется вдвое меньше раз, чем на предыдущей итерации

Общее количество итераций равно N N/2 N/4 … 1, что примерно равно 2N.

Следовательно, общее количество итераций равно O(N)

Комментарии:

1. На первой итерации внешнего цикла внутренний цикл выполняется N раз. На второй итерации внутренний цикл выполняется N/2 раза. Итак, код выполняется более N раз, почему временная сложность O(N). Разве это не должно быть O(N*log N) ? @Эллиотт

2. Это геометрическая последовательность с q = 1/2

3. @UnknownHuman, вы поймете, почему r3mainder это правильно, если узнаете о том, как суммировать геометрическую последовательность.

4. О, хорошо. Теперь я это понял. Его временная сложность равна O(n log n), которая записывается как O(n). Спасибо. Это был непростой вопрос, по крайней мере, для начинающих..

5. @UnknownHuman, извините, но это еще не все. На самом деле это примерно O(2N) так , но мы отбрасываем постоянные факторы, так что это становится O(N)

Метки: