Можно ли обратить этот алгоритм вспять за время, превышающее O(N^2)? ⇐ Python

[Гость]

Скажем, у меня есть следующий алгоритм для бижектирования bytes -> Natural:

def Rank(s: байты) -> int: к = 2**8 результат = 0 смещение = 0 для i, w в перечислении(ях): результат *= к результат += ш смещение += (к**и) вернуть результат + смещение Декодер (по крайней мере, в меру моих ограниченных возможностей) выглядит следующим образом:

def unrank(value: int) -> байты: к = 2**8 # 1. Получите длину импортировать itertools смещение = 0 для длины в itertools.count(): #! ЦИКЛ ВЫПОЛНЯЕТСЯ O(N) РАЗ !# смещение += (k**длина) #! ДЛИННОЕ СЛОЖЕНИЕ ЕСТЬ O(N) !# если смещение > значение: значение = значение - (смещение - k**длина) перерыв # 2. Получите ценность результат = байтовый массив (длина) для i в обратном порядке (диапазон (длина)): value, result = divmod(value, k) # (можно сделать с помощью битовых сдвигов, игнорируйте из-за сложности) вернуть байты (результат) Полагая, что N ≈ len(bytes) ≈ log(int), этот декодер явно имеет время выполнения в наихудшем случае O(N^2). Конечно, он работает хорошо (время выполнения