Почему большие входные размеры подразумевают более сложные случаи?

12

Ниже предположим, что мы работаем с машиной Тьюринга с бесконечной лентой.

Объясняя кому-то понятие временной сложности и почему оно измеряется относительно входного размера экземпляра, я наткнулся на следующее утверждение:

[..] Например, естественно, что вам нужно больше шагов для умножения двух целых чисел на 100000 бит, чем, скажем, умножение двух целых чисел на 3 бита.

Претензия убедительна, но как-то махает рукой. Во всех алгоритмах, с которыми я сталкивался, чем больше размер ввода, тем больше шагов вам нужно. В более точных словах, сложность времени является монотонно возрастающей функцией размера ввода.

Это тот случай, когда сложность времени всегда увеличивается в зависимости от размера ввода? Если так, то почему? Есть ли доказательства этому помимо махнув рукой?

Кава
источник
«Прямо пропорциональный» имеет конкретное математическое значение, которое означает, по существу, линейное время. Другими словами, если ваш вход имеет размер , если время прямо пропорционально, алгоритм выполняется во времени c n . Я полагаю, это не то, что вы имеете в виду, так как многие алгоритмы не работают за линейное время, то есть сортировка. Можешь объяснить дальше? ncn
SamM
Итак, вы спрашиваете об алгоритме, который выполняется за времени? O ( 1 ) означает, что алгоритм работает в одно и то же время независимо от размера ввода, o ( 1 ) означает, что он работает быстрее по мере увеличения ввода. Я не могу вспомнить тот, который запускается в то время вне моей головы, но обозначения довольно распространены, потому что алгоритм часто запускается примерно во время O ( n 2 ) + o ( 1 ) - другими словами требуется O ( n 2 )o(1)O(1)o(1)O(n2)+o(1)O(n2)время, и есть некоторые другие термины, которые становятся меньше по мере увеличения ввода.
SamM
Хороший вопрос. Как насчет контр-примера вычисления простых множителей для некоторого большого c (это только возрастающая функция для n c )? @Sam Обратите внимание, что возрастающая функция говорит, что время должно уменьшаться в некоторой точке вдоль реальной линии (т.е. f ( b ) < f ( a ) , a < b ). c/ncncf(b)<f(a),a<b
Кейси Кубалл
@ Дарфетт Боюсь, я не пойду. Не все увеличивающиеся функции уменьшаются в некоторой точке вдоль реальной линии.
SamM
@ Дженнифер Да, я понимаю, это имеет смысл. Я бы рекомендовал использовать термин как он имеет значение, которое вы ищете. И я хотел бы еще раз подчеркнуть, что прямая пропорциональность подразумевает линейность; Я понимаю, к чему вы клоните, но это может смутить тех, кто читает вопрос впервые. o(1)
SamM

Ответы:

12

Это тот случай, когда сложность времени всегда увеличивается в зависимости от размера ввода? Если так, то почему?

Рассмотрим машину Тьюринга, которая останавливается после шагов, когда входной размер n четный, и останавливается после n 2 шагов, если n нечетно.nnn2n

Если вы имеете в виду сложность проблемы , ответ по-прежнему нет. Сложность проверки простоты намного меньше для четных чисел, чем для нечетных.

JeffE
источник
4

Это тот случай, когда сложность времени всегда увеличивается в зависимости от размера ввода? Если так, то почему? Есть ли доказательства этому помимо махнув рукой?

nnn/cc


n=1n>1


Вероятно , интерес представляют сублинейные алгоритмы , которые не читают весь ввод. Смотрите, например, http://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/Sublinear-time-Survey-BEATCS.pdf .

Кристофер
источник
O(logn)o(1)
@Sam: Извините, я не видел ваш комментарий перед редактированием (добавление сублинейных алгоритмов).
Кристофер
наоборот; Я не видел ваших правок перед добавлением комментария. Я бы удалил его, но вторая половина все еще применяется, и дополнительная ссылка не может повредить OP
SamM
1
f(x)=0
1

(N,)Ω(1)

Тем не менее, среднее время выполнения может содержать колеблющиеся компоненты, например, Mergesort .

Рафаэль
источник
Я не вижу, как этот ответ связан с вопросом.
А.Шульц
@ A.Schulz Это дает доказательство для основного вопроса: «Является ли это случаем, что сложность времени всегда является увеличивающейся функцией в размере входного сигнала?», Читая «увеличивающийся» как «неубывающий», то есть не обязательно сильно увеличивающийся.
Рафаэль
1
@ A.Schulz: Тем не менее, моя интерпретация, кажется, то, что интересует Дженнифер .
Рафаэль