Объясните, почему сложность времени для суммирования цифр в количестве длины N равна O (logN)

Question

Вот код:

int sumDigits(int n) {
    int sum = 0;

    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }

    return sum;
}

Я понимаю этот код, и этот код будет занимать одну цифру, добавлять эту цифру к сумме и удалять эту цифру. Он продолжает делать это до тех пор, пока n не станет равно 0, и в этот момент он вернет сумму. Интуитивно понятно, что во время выполнения будет количество цифр в числе N. Но я не понимаю, почему эта временная сложность равна O (logN). Я думал, что это O (N).

Даже с объяснениями вроде: «Число с цифрами d может иметь значение до 10 ^ d. Если n = 10 ^ d, то d = log n. Следовательно, время выполнения равно O (logN)». не полностью нажмите.

Я следую первой части, что если d, скажем, 3, то значение <10 ^ d == значение <1000. Значение max равно 999 с числом длины 3, с которым я согласен. Но после этого, когда они устанавливают связь, что, если n = 10 ^ d, я не понимаю, как 1) они знали, что такое равенство и 2) как это делает сложность O (logN), а не O (N). </p>

Answer 1

Вы путаете два определения N здесь. Ваш текст цитирует это как само число; Ваше последнее описание рассматривает N как количество цифр. Да, алгоритм: O (цифры) сложность ... но количество цифр примерно равно log10 (N) , где N - это число.

Answer 2

Сложность пропорциональна количеству цифр. В конце концов, если в номере 2,351 цифра, цикл while будет повторяться 2,351 раза.

Таким образом, вопрос сводится к тому, «сколько цифр в N, асимптотически?». Число с d цифрами составляет от 10^(d-1) включительно до 10^d включительно. Другими словами, пусть d будет количеством цифр в N, и мы получим неравенства 10^(d-1) <= N < 10^d. Взяв логарифм, мы имеем d-1 <= log(N) < d. (Мы можем поддерживать неравенства, потому что логарифмы монотонны.) Добавление 1 к левому неравенству дает d <= log(N) + 1, а в сочетании с предыдущим результатом мы имеем log(N) < d <= log(N) + 1. То есть число цифр d ограничено сверху и снизу с помощью терминов O(log(N)).

Выше показано, что количество цифр равно O(log(N)) или, точнее, Theta(log(N)). Сложность времени такая же, поскольку она пропорциональна количеству цифр.