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

13

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

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

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

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

Существуют и другие проблемы, заключающиеся в том, что даже если входным набором являются числа, они описывают «длину ввода» как «переменные решения», поэтому для входного набора длины N с числами в диапазоне длина ввода равна просто N (например, сумма подмножества), или еще более усложняют количество двоичных значений места, которое требуется для постановки задачи (я считаю, что это то же самое, что ) N l o g ( L )0232Nlog(L)

Так:

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

Ответы:

10

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

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

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

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

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

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

Люк Мэтисон
источник
Спасибо за ответ. Действительно интересная часть, о которой вы говорите о выборе правильного прокси, чтобы говорить о членстве в P или NP для ввода, это может быть совершенно новый вопрос! Кроме того, и возвращаясь к прежнему вопросу. Какой из них, по вашему мнению, будет лучшим прокси для алгоритма, в котором его вход представляет собой набор целых чисел? Наверное, может это будет зависеть от алгоритма? Я вижу 3 возможных варианта: N (длина набора), N * Log (L) (L - максимальное значение) и Log (сумма (набор)).
Иисус Салас
NlogLNN 2logL
5ccn2lognnn2
Возможно, когда использовать N или N, log L может зависеть от стоимости алгоритма для работы с каждым входным элементом. Я предполагаю, что если у нас есть предположение, что алгоритм использует постоянное время для выполнения своей работы над каждым входным элементом независимо от его размера в битах (и этим не злоупотребляют), то N, вероятно, является правильным, что приводит к O (N) , С другой стороны, если размер входного элемента в битах увеличивает стоимость операции, тогда N log L кажется более точным, поскольку в верхней границе мы должны выразить, какие свойства из входных данных участвуют в росте
Иисус Салас
5c=1c=log255 O(n2logn)биты, но это довольно надежная верхняя граница, которая может работать как с обычными кодировками.
Люк Мэтисон
8

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

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

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

  • O(nlogn)nO(1)n
  • n×n

n

A.Schulz
источник
1
nO(n3)nn