Ниже предположим, что мы работаем с машиной Тьюринга с бесконечной лентой.
Объясняя кому-то понятие временной сложности и почему оно измеряется относительно входного размера экземпляра, я наткнулся на следующее утверждение:
[..] Например, естественно, что вам нужно больше шагов для умножения двух целых чисел на 100000 бит, чем, скажем, умножение двух целых чисел на 3 бита.
Претензия убедительна, но как-то махает рукой. Во всех алгоритмах, с которыми я сталкивался, чем больше размер ввода, тем больше шагов вам нужно. В более точных словах, сложность времени является монотонно возрастающей функцией размера ввода.
Это тот случай, когда сложность времени всегда увеличивается в зависимости от размера ввода? Если так, то почему? Есть ли доказательства этому помимо махнув рукой?
Ответы:
Рассмотрим машину Тьюринга, которая останавливается после шагов, когда входной размер n четный, и останавливается после n 2 шагов, если n нечетно.n n n2 n
Если вы имеете в виду сложность проблемы , ответ по-прежнему нет. Сложность проверки простоты намного меньше для четных чисел, чем для нечетных.
источник
Вероятно , интерес представляют сублинейные алгоритмы , которые не читают весь ввод. Смотрите, например, http://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/Sublinear-time-Survey-BEATCS.pdf .
источник
Тем не менее, среднее время выполнения может содержать колеблющиеся компоненты, например, Mergesort .
источник