Какая сложность у этого алгоритма?

Question

[Pitonoslav]

Прохожу курс по алгоритмам, есть задача где нужно оценить сложность, есть объяснение автора, но я не до конца понимаю и мне кажется здесь есть ошибка..

Задача:
Рассмотрим следующую функцию, которая считает сумму цифр всех чисел в массиве. Пусть a – массив размера
N, а элементы этого массива – целые неотрицательные числа, не больше С. Дайте наиболее точную оценку асимптотики времени работы этой функции.

Код:

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

Оценка сложности данного кода - O(N*log C), а мне кажется что O(N*C).

Объяснение автора:

Оценим сначала асимптотику времени работы внутреннего цикла while: того, который считает сумму цифр одного числа.

На каждой итерации этого цикла значение value уменьшается хотя бы в 10 раз (значение может уменьшиться чуть сильнее, чем в 10 раз, из-за округления при целочисленном делении). Значит, если прошло k итераций цикла, то значение value уменьшится хотя бы в 10^k раз. Так как исходно значение не превышало C, получаем, что 10^k <= C, значит k <= logC. Таким образом, асимптотика времени работы внутреннего цикла while составляет O(log C)
Так как этот цикл независимо запускается N раз, итоговая асимптотика времени работы программы составляет
O(N⋅logC).

Я не понимаю почему O(N*logC), а не O(N*C). Цикл while же выполняется пропорционально количеству цифр в числе..

Answer 1

[Rsa97]

Цикл while же выполняется пропорционально количеству цифр в числе..

Да. А количество цифр в числе C это ⌊log₁₀C⌋ + 1.
Элемент суммы с меньшей степенью (1) отбрасываем, округление вниз убираем, основание логарифма неважно, получаем logC

Comments

[Pitonoslav]

т.е. временная сложность также зависит от конкретного способа подсчета количества итераций?

[Rsa97]

Vladislav, От способа подсчёта ничего зависеть не должно. У вас же, например, результат умножения не зависит от того, умножаете вы в столбик на бумаге или вычисляете на калькуляторе.

[Pitonoslav]

Rsa97, если "не зависит", количество итерацией растёт линейно количеству цифр в числе т.е. параллельно линейному росту(а он таковым является по факту) и мы берём для оценки худший случай, то почему для оценки сложности это не O(n)?

[Rsa97]

Vladislav, Каким бы способом вы ни считали количество цифр целого числа, у вас всё равно получится логарифм от величины числа.

[Pitonoslav]

Rsa97, но почему для оценки мы за C берём само число, а не количество цифр в этом числе?

[Rsa97]

Pitonoslav, Потому что сложность принято считать от параметров - величины значений и/или размеров массивов.