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

Question

Я видел проблемы с кодированием, которые похожи на это:

int doSomething(String s) 

Когда в описании проблемы говорится, что s будет содержать не более одного символа, поэтому s не может быть больше, чем длина 26. Я думаю, что в этом случае итерация по s будет постоянным временем.

Но я также видел проблемы, когда входные данные ограничены случайным большим числом, таким как 10 ^ 5, просто чтобы избежать переполнения стека и других странных крайних случаев. Если мы собираемся рассматривать входы, которые ограничены константами, как постоянную сложность, не должны ли эти входы также считаться постоянной сложностью?

Но мне не имеет смысла считать s сложности O (n), потому что было много проблем, когда люди выделяли массивы char [26] для хранения каждой буквы алфавита. Как, если имеет смысл считать, что входные данные, которые, как мы знаем, будут меньше или равны 26, будут иметь большую сложность, чем массив размером 26?

Answer 1

Смысл анализа сложности алгоритмов состоит в том, чтобы оценить, сколько времени потребуется для его запуска. Если проблема, которую вы пытаетесь решить, ограничивает максимальное значение n константой, вы можете считать n константой, и вы не ошибетесь. Но будет ли это полезно, если вы хотите предсказать, будет ли алгоритм, выполняющий операции 2^n, работать за несколько секунд для n = 26? С другой стороны, если у вас был алгоритм, который выполняет n*m операций, а m - самое большее 3, насколько было бы полезно включить m в анализ сложности?

Answer 2

При вычислении сложности основное внимание уделяется тому, что является наиболее важной переменной, связанной со временем выполнения. Если время выполнения доминирует по длине s, это наш главный фокус анализа сложности, и это должно быть в нотации bi gO. И в этом случае, конечно, это не константа.

Если вход ограничен большим числом, например 10 ^ 5.

И если алгоритм становится медленнее, пропорционально этому входу.

например,

int sort(string s); //length of s is less than 10^5

В этом случае, в зависимости от того, какой алгоритм сортировки вы используете, время выполнения будет пропорционально длине s

как O(n^2) or O(nlogn) если n - это длина s

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

Но если алгоритм Внутренняя часть не имеет ничего общего с длиной s, так как она имеет постоянное время вычисления, тогда вы можете сказать, что ограничение 10 ^ 5 является просто константой.