Точный размер ввода и сложность времени

Question

Когда мы говорим о сложности времени, мы обычно используем n в качестве входных данных, что не является точной мерой фактического размера ввода.У меня возникают проблемы с показом, что при использовании определенного размера для ввода ( s ) алгоритм остается в том же классе сложности.

Например, возьмите простой алгоритм последовательного поиска.В худшем случае это занимает W (n) время.Если мы применяем конкретный размер ввода (в базе 2), порядок должен быть W (lg L), где L - наибольшее целое число.

Как мне показать, что последовательный поиск или любой алгоритм,остается тот же самый класс сложности, в данном случае линейное время? Я понимаю, что есть какая-то замена, которая должна иметь место, но я неуверен в том, как прийти к заключению.

РЕДАКТИРОВАТЬ

Я думаю, что, возможно, я нашел то, что искал, но я не совсем уверен.максимальное количество шагов, выполненных алгоритмом для входного размера s, затем по определению входного значения размер , s = lg n, где n - это входное значение.Тогда n = 2 ^ s, что приводит к выводу, что сложность по времени равна W (2 ^ s), экспоненциальная сложность.Следовательно, производительность алгоритма с двоичным кодированием является экспоненциальной, а не линейной, как в терминах величины.

Answer 1

Говоря о сложности времени, мы обычно используем n в качестве входных данных, что не является точной мерой фактического размера ввода. У меня возникают проблемы с показом, что при использовании определенного размера для входных данных алгоритм остается в том же классе сложности.

Например, возьмите простой алгоритм последовательного поиска. В худшем случае это занимает W (n) время. Если мы применим конкретный размер ввода (в базе 2), порядок должен быть W (lg L), где L - наибольшее целое число.

L - это переменная, представляющая наибольшее целое число. n - это переменная, представляющая размер ввода. L не является конкретным значением больше, чем n .

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

Допустим, вы ищете список из 500 целых чисел. Другими словами, n = 500

Класс сложности наихудшего случая последовательного поиска: O (n)

Сложность n

Конкретный случай сложности наихудшего случая - 500

---

Edit:

Ваши значения будут одинаковыми по количеству битов, необходимых для кодирования каждого значения. Если вход представляет собой список 32-битных целых чисел, то c = 32, число бит на целое число. Сложность будет 32 * n => O (n).

В терминах L, если L - наибольшее значение, а lg L - количество битов, необходимых для кодирования L, то lg L - это константа c. Ваша сложность в терминах битов: O (n) = c * n, где c = lg L - постоянный конкретный размер ввода.

Answer 2

Что я знаю, так это то, что максимальное число шагов, выполняемых последовательным поиском, очевидно, равно cn ^ 2 + nlg L. cn ^ 2 - это количество шагов для увеличения циклов и выполнения ветвления.1003 *

Это совсем не так.Максимальное количество шагов, выполняемых последовательным поиском, будет равно c * n, где n - количество элементов в списке, а c - некоторая константа.Это худший случай.Нет n ^ 2 компонента или логарифмического компонента.

Например, простой последовательный поиск будет выглядеть так:

for (int i = 0; i < NumItems; ++i)
{
    if (Items[i] == query)
        return i;
}
return -1;

При использовании этого алгоритма, если вы будете искать каждый элемент, то половинадля поиска потребуется менее NumItems/2 итераций, а для половины запросов потребуется NumItems/2 или более итераций.Если искомого элемента нет в списке, для его определения потребуется NumItems итераций.Худшее время выполнения - NumItems итераций.Средний случай - NumItems/2 итераций.

Фактическое число выполненных операций - это некоторая постоянная C, умноженная на количество итераций.В среднем это C*NumItems/2.

Answer 3

Как утверждает Люсия Мура: «За исключением унарного кодирования, все другие кодировки для натуральных чисел имеют длины, которые связаны полиномиально»

Здесь - этоисточник.Посмотрите на страницу 19.