Ohodnoťte algoritmickou složitost řešení problému palindromu. Z hlediska času a paměti. Pokud je abeceda pevná (anglické písmena, 26 znaků), jaká je složitost z hlediska paměti?

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

• По времени: алгоритм проходит по строке максимум один раз, сравнивая пары символов, поэтому временная сложность — O(n), где n — длина строки.
• По памяти: если не создавать дополнительных структур, а сравнивать символы на месте, дополнительная память не требуется, то есть O(1).

Если алфавит фиксированный (например, 26 английских букв), и задача требует учитывать частоты символов или использовать вспомогательные структуры, то по памяти можно выделить массив фиксированного размера 26 элементов, что даёт O(1) по памяти, так как размер массива не зависит от длины строки.

Пример проверки палиндрома на Java:

boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) return false;
        left++;
        right--;
    }
    return true;
}