Я прохожу курс по алгоритмам и столкнулся с задачей, где необходимо оценить сложность. Есть объяснение от автора, и я не до конца с ним согласен, так как мне кажется, что в нем есть ошибка.
Задача: Рассмотрим функцию, которая вычисляет сумму цифр всех чисел в массиве. Пусть a — массив размера N, содержащий целые неотрицательные числа, не превышающие C. Какова наиболее точная оценка асимптотической сложности времени работы этой функции?
Код:
<pre><code class="python">def count_digit_sum(N, a):
sum = 0
for i in range(N):
value = a[i]
while value > 0:
sum += value % 10
value //= 10
return sum</code></pre>
Автор оценивает сложность данного кода как O(N * log C), а я предполагаю, что это O(N * C).
Объяснение автора:
<blockquote>
Сначала проанализируем асимптотику времени работы внутреннего цикла while, который считает сумму цифр одного числа. На каждой итерации этого цикла значение переменной value уменьшается хотя бы в 10 раз. Это означает, что после k итераций значение value уменьшится хотя бы в 10^k раз. Так как начальное значение не превышало C, мы получаем 10^k ≤ C, что означает k ≤ logC. Таким образом, асимптотика времени работы внутреннего цикла while составляет O(log C). Поскольку данный цикл запускается N раз, итоговая асимптотика времени работы программы составит O(N * log C).
</blockquote>
Я не понимаю, почему сложность составляют O(N * log C), а не O(N * C), ведь цикл while выполняется пропорционально количеству цифр в числе.
Давайте разберем алгоритм и проанализируем временную сложность более подробно. Код функции `count_digit_sum` и его логика такова: 1. Мы проходим по всем элементам массива `a` длины `N`. 2. Для каждого элемента (числа) `value`, мы суммируем его цифры, используя цикл `while`. Теперь посмотрим на то, сколько раз выполняется внутренний цикл `while`: - Внутренний цикл `while` выполняется, пока `value` больше 0. - На каждой итерации цикла мы уменьшаем `value`, деля его на 10, что фактически приводит к тому, что `value` теряет по одной цифре. Таким образом, количество итераций внутреннего цикла `while` можно оценить как количество цифр в числе `value`. Если максимальное значение в массиве `a` равно `C`, то количество цифр в числе можно выразить как: - Количество цифр в `C` пропорционально `log10(C)`. Это значит, что внутренний цикл `while` выполняется O(log C) раз для каждого элемента массива. Поскольку мы проходим по всем `N` элементам массива, общая временная сложность будет: - Время работы = O(N) (количество элементов) * O(log C) (количество итераций на элемент). Таким образом, асимптотическая сложность алгоритма составит O(N * log C), что и утверждает автор. Ваше предположение о том, что сложность может быть O(N * C), неправильно. Это возникло бы, если бы каждый элемент проходился за время, пропорциональное его значению, а не количеству его цифр. Но в данном случае скорость работы внутреннего цикла зависит не от самого числа, а от количества его цифр, что и приводит нас к O(log C). В заключение, правильная оценка сложности данного алгоритма действительно O(N * log C).
Цикл while же выполняется пропорционально количеству цифр в числе..Да. А количество цифр в числе C это ⌊log
Элемент суммы с меньшей степенью (1) отбрасываем, округление вниз убираем, основание логарифма неважно, получаем logC