алгоритм времени анализа «входной размер» против «входных элементов»

Я все еще немного путаюсь с терминами «длина ввода» и «размер ввода», когда они используются для анализа и описания бессимптомной верхней границы для алгоритма.

Кажется, что длина входного сигнала для алгоритма зависит от типа данных и алгоритма, о котором вы говорите.

Некоторые авторы ссылаются на длину ввода для размера символов, которые требуются для представления ввода, поэтому «abcde», если его использовать в качестве набора ввода в алгоритме, будет иметь «длину ввода» 6 символов.

Если вместо символов у нас есть число (например, целые числа), то иногда вместо символов используется двоичное представление, поэтому «длина ввода» вычисляется как $N*log(L)$ (если L - максимальное число во входном наборе) ,

Существуют и другие проблемы, заключающиеся в том, что даже если входным набором являются числа, они описывают «длину ввода» как «переменные решения», поэтому для входного набора длины N с числами в диапазоне длина ввода равна просто N (например, сумма подмножества), или еще более усложняют количество двоичных значений места, которое требуется для постановки задачи (я считаю, что это то же самое, что ) N ∗ l o g ( L $0-2^{32}$$N*log(L)$

Так:

• это зависит от алгоритма?
• Что означает и когда использовать каждую длину ввода "версия"
• Есть ли какое-то правило, которое я могу использовать, чтобы решить, какое из них использовать?

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

Это, конечно, довольно абстрактно, и очень трудно работать на практике, или, по крайней мере, очень раздражает - нам нужно подумать о том, как мы собираемся указывать разделители и т. Д. И т. Д. На практике обычно происходит то, что мы ищем проксите измерение размера входных данных - что - то более удобное и доступное, но это не вызывает какие - либо математические задачи в нашем анализе.

Используя ваш пример «abcde», обычно бывают случаи, когда алфавит, который мы используем для ввода, невелик, поэтому даже при использовании прокси-измерения символов мы знаем, что даже на машине Тьюринга мы можем, если нам надоело, укажите входную кодировку, которая будет преобразовывать «abcde» в некоторую закодированную форму, которая имеет длину не более 5 × c для некоторой константы c . Такое расширение на константу, как правило, не имеет значения в нашем асимптотическом анализе, поскольку мы регулярно отбрасываем постоянные факторы.$5$$5\times c$ $c$

В другом случае мы часто измеряем размер входного графа по количеству вершин . Ясно, что если мы хотим указать сколь угодно большие графы, размер закодированного ввода не просто n - что случилось с краями, например? Что мы знаем, так это то, что мы можем использовать разумную схему кодирования, которая представляет граф в виде N = c ⋅ n 2 log n битов. Это скорее расширение, чем константа, но во многих интересных случаях мы имеем дело только с гранулярностью, и многочлены хорошо сочетаются разными способами, в частности, например, если мы определяем, что наше время работы O ( p $n$$n$$N = c\cdot n^{2}\log n$ где p - многочлен, то мы знаем, что существует некоторый многочлен p ′ такой, что O ( p ( n ) ) = O ( p ′ ( N ) ) , поэтому, когда мы вернемся к формальной мере входа Мы все еще в полиномиальном времени.$O(p(n))$$p$$p'$$O(p(n)) = O(p'(N))$

Место, где это может упасть, это когда вы работаете с числами. Так как число с величиной может быть закодировано в n = O ( log m ) битах, если бы наше время работы было O ( m ) , это было бы O ( 2 n ) - экспоненциальный по фактическому размеру входного сигнала - что сделало бы величину м плохой выбор для прокси для размера ввода, если мы хотим поговорить о членстве в P, например (когда вы приходите к Strongly- N P -complete и Weakly- N $m$$n = O(\log m)$$O(m)$$O(2^{n})$$m$$\mathcal{P}$$\mathcal{NP}$$\mathcal{NP}$-полный, запомни это). С другой стороны, если бы все, что нас интересовало, было решимостью, то это была бы достаточно хорошая мера по доверенности.

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

Это зависит от вашей модели вычислений, а также, к сожалению, иногда от самого алгоритма.

• $ababcd$
• Если ваша модель - это ОЗУ, то размер входа - это количество регистров / ячеек памяти, где изначально находится вход. Это может быть использовано неправильно, поскольку технически вы можете записать весь ввод в один регистр. Однако тогда вычисления будут более затратными, если вы используете модель логарифмических затрат.
• $w$$w$

Однако многие алгоритмы не измеряются относительно «фактического» размера ввода. Затем вы должны внимательно посмотреть, к чему относится утверждение анализа.

• $O(n\log n)$$n$$O(1)$$n$
• $n\times n$

$n$