Большой O для конечного набора возможных значений фиксированного размера

Сложность имеет значение только в том случае, если есть переменная N. Таким образом, вопрос не имеет смысла сам по себе. Если вопрос был:

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

Является ли второй алгоритм O (1) или O (N)?

Тогда ответ будет таким: этот алгоритм — O(N).

Большой O описывает, как производительность алгоритма будет масштабироваться по мере увеличения входного размера n. Другими словами, когда вы запускаете алгоритм с большим количеством входных данных.

В этом случае входные данные имеют фиксированный размер, поэтому оба алгоритма имеют значение O (1), хотя и с разными постоянными коэффициентами.

Если вы взяли «n» для обозначения количества битов в числах (т. Е. Вы сняли ограничение на 64-битную длину), то вы могли бы проанализировать для заданного битового размера n, как масштабируются алгоритмы.

В этом сценарии первый все еще будет O(1) (см. комментарий Qnan), а второй теперь будет O(2^n).

Я настоятельно рекомендую посмотреть первые лекции от курс Массачусетского технологического института "Введение в алгоритмы". Они прекрасно объясняют Большой О (и Большой Омега/Тета), хотя и предполагают хорошее понимание математики.

Проверка каждого возможного ввода - это O (2 ^ N) по количеству битов в решении. Когда вы делаете количество битов постоянным, тогда оба алгоритма имеют значение O (1), вы знаете, сколько решений вам нужно проверить.

Факт: Каждый алгоритм, который вы на самом деле запускаете на своем компьютере, равен O(1), потому что Вселенная имеет конечную вычислительную мощность (есть конечное количество атомов и конечное количество секунд, прошедших с момента Большого взрыва).

Это правда, но не очень полезный способ думать о вещах. Когда мы используем большой O на практике, мы обычно предполагаем, что задействованные константы малы по сравнению с асимптотическими членами, потому что в противном случае только указание асимптотического члена мало что скажет вам о том, как работает алгоритм. Это прекрасно работает на практике, потому что константы обычно представляют собой такие вещи, как «использую ли я массив или хэш-карту», ​​которые отличаются не более чем в 30 раз, а входные данные равны 10 ^ 6 или 10 ^ 9, поэтому разница между квадратичным и линейный алгоритм более важен, чем постоянные факторы. Обсуждения большого O, которые не соблюдают это соглашение (например, алгоритм № 2), бессмысленны.

Каким бы ни было значение для a или b, в худшем случае по-прежнему нужно проверять значения 2^64, 2^32 или 2^somevalue. Сложность этого алгоритма составляет время O(2^k), где k — количество битов, используемых для представления длинного значения, или время O(1), если мы рассматриваем значения a и b.