Какова временная сложность печати целого числа?
Я пытаюсь понять временную сложность простой программы, печатающей целое число. Код Python выглядит следующим образом:
n = 123456789
print(n)
Сначала я думал, что сложность O(1), поскольку печать кажется операцией с постоянным временем. Однако, учитывая, что n имеет цифры мм, где m≈log10(n)+1, кажется, что печать каждой цифры займет O(1) время, что усложнит общую сложность O(m).
Учитывая, что m — это количество цифр, пропорциональное log10(n), означает ли это, что временная сложность на самом деле равна O(logn)?
Может ли кто-нибудь уточнить, равна ли временная сложность печати целого числа O(1) или O(logn)? Если это O(logn), не могли бы вы объяснить почему подробнее?
Спасибо!
@jasonharper, ты имеешь в виду, что это точно нет O(1)?
Этого абсолютно не может быть O(1), учитывая, что объем вывода разный!
Поскольку размер вывода равен O(log n), а каждая цифра должна стоить вам еще O(log n), общая сложность должна быть близка к O(log^2(n)). Эксперименты с Python подтверждают, что время выполнения примерно пропорционально квадрату количества цифр (для чисел до 1000000 десятичных цифр).
С практической точки зрения это O(1). Если вы хотите узнать точный результат и вам действительно очень хочется это знать, вам нужно проверить, как он реализован, как хранятся цифры/биты, как они преобразуются в символы, как они отправляются, например. стандартный выход и т. д. В 99,99999% случаев это не имеет значения, и его можно считать O(1).
@ luk2302, как существует «практическая» точка зрения на большое О? Большой О касается асимптотического поведения, а не 99,99999% случаев.
Это в некоторой степени зависит от контекста. Часто при анализе алгоритмов неявно предполагается, что существует фиксированный максимальный размер для всех целых величин, если только из контекста не очевидно, что программа предназначена для работы со значениями произвольной точности («большими числами»). При этом предположении печать действительно занимает O(1), поскольку количество цифр также ограничено фиксированной константой.
Ответы 1
Временная сложность печати целых чисел в Python равна O(log(n)^2), что можно увидеть, наблюдая за временем, затрачиваемым на str(n) для все более больших n (Python 3.10.12 в Linux):
$ python3 -m timeit -s 'n=1<<512' 'str(n)'
100000 loops, best of 5: 1.4 usec per loop
$ python3 -m timeit -s 'n=1<<1024' 'str(n)'
50000 loops, best of 5: 4.46 usec per loop
$ python3 -m timeit -s 'n=1<<2048' 'str(n)'
10000 loops, best of 5: 15.9 usec per loop
$ python3 -m timeit -s 'n=1<<4096' 'str(n)'
5000 loops, best of 5: 59.5 usec per loop
$ python3 -m timeit -s 'n=1<<8192' 'str(n)'
1000 loops, best of 5: 231 usec per loop
Каждый раз, когда мы удваиваем размер n (удваиваем log(n)), количество времени увеличивается в 4 раза, что почти идеально соответствует O(log(n)^2).
Почему это O(log(n)^2)? Получение каждой цифры вывода включает многократное деление числа на 10. Само деление требует времени, пропорционального длине числа. Следовательно, мы делаем O(log(n)) делений, каждое из которых стоит O(log(n)) времени.
Мы можем добиться гораздо большей временной сложности, используя шестнадцатеричное представление, а не десятичное. Поскольку числа внутренне представлены в двоичном формате, преобразование в шестнадцатеричное не требует деления; вместо этого каждая группа из четырех битов напрямую преобразуется в соответствующую шестнадцатеричную цифру. Таким образом, мы ожидаем, что временная сложность шестнадцатеричного вывода будет равна O(log(n)), и это именно то, что мы видим:
$ python3 -m timeit -s 'n=10**150' 'hex(n)'
500000 loops, best of 5: 325 nsec per loop
$ python3 -m timeit -s 'n=10**300' 'hex(n)'
500000 loops, best of 5: 554 nsec per loop
$ python3 -m timeit -s 'n=10**600' 'hex(n)'
200000 loops, best of 5: 1.04 usec per loop
$ python3 -m timeit -s 'n=10**1200' 'hex(n)'
100000 loops, best of 5: 2 usec per loop
$ python3 -m timeit -s 'n=10**2400' 'hex(n)'
50000 loops, best of 5: 3.9 usec per loop
Здесь я использую степени десяти, сравнимые по размеру с приведенными выше двоичными числами, чтобы не просто выводить длинные строки нулей.
Квадратичная сложность преобразования больших чисел в десятичные числа и обратно привела к тому, что Python ввел ограничения на длину десятичных чисел в Python 3.11, чтобы избежать атак типа «отказ в обслуживании»; см. https://docs.python.org/3/library/stdtypes.html#int-max-str-digits для более подробной информации. В этом документе также упоминается алгоритм субквадратичной сложности. Точная сложность этого алгоритма зависит от используемого алгоритма деления. Он не используется в Python, поскольку его немного сложнее реализовать, но он реализован в GNU GMP (доступен через пакет gmpy).
Это было бы так же быстро, как
O(logn), если бы вы могли воспроизводить каждую цифру числа за постоянное время. Это было бы разумным предположением для системы счисления степени 2, такой как шестнадцатеричная, но это явно неверно для десятичной системы: извлечение каждой цифры - это, по сути, операция деления с остатком, которая займет время, которое зависит от величины номер. Точный ответ будет зависеть от используемого алгоритма деления.