Ответ
Когда запрашивается временная или пространственная сложность алгоритма в терминах n, вам необходимо определить, что такое n.
Линейное сканирование массива n символов, как вы знаете, имеет временную сложность O(n). Поскольку вы применяете этот же алгоритм к своему массиву из <= 128 символов, вы, безусловно, можете сказать, что применяете алгоритм <code>O(n) к своему массиву.
Однако, если вы определите алгоритм как «сканирование через массив символов максимум 128 символов», тогда ваш алгоритм действительно будет иметь временную сложность O(1), потому что его число операций ограничено сверху константой.
Итак, чтобы ответить на ваш вопрос: это вопрос перспективы. Как вы определяете свой алгоритм?
- "Обобщенное сканирование массива длины
n"? Тогда это O(n), где n в вашем конкретном приложении никогда не превышает 128 (хорошо для вас).
- "Сканирование 128 или менее символов"? Тогда это
O(1), потому что его время ограничено сверху постоянной.
Философия немного дальше
Теперь, даже если бы вы увеличили длину массива, чтобы заполнить всю вашу оперативную память, какой бы большой она ни была, это все равно конечное целое число, и поэтому вы математически были бы абсолютно правы, утверждая, что он будет работать в O(1) раз. Однако! Насколько уместно определить алгоритм, который просматривает массив, который помещается в вашу RAM? Мы только что значительно снизили полезность нашего алгоритма, потому что, если, скажем, у меня больше оперативной памяти, чем у вас, тогда ваш алгоритм не будет отвечать моим потребностям.
Именно поэтому мы используем параметр n, чтобы обозначить некоторую метрику (здесь длина массива). Это позволяет нам определить алгоритм сканирования, который работает для входов ЛЮБОГО (!) Размера. Как вы знаете, этот алгоритм в лучшем случае O(n), который может звучать не так хорошо, как O(1), но теперь это общий алгоритм, который можно использовать для любого размера ввода, а не тот, в который мы включили ограничение ввода. как часть самого алгоритма.