Какая средняя алгоритмическая сложность (по времени) для операции "my_string.lower()" в Python?

Сложность операции lower() для строк

Операция string.lower() в Python имеет алгоритмическую сложность O(n), где n — длина строки. Это означает, что время выполнения операции прямо пропорционально количеству символов в строке.

Почему O(n)?

Метод lower() должен пройти через каждый символ строки и преобразовать его в нижний регистр (если это возможно). Вот что происходит под капотом:

my_string = "HELLO WORLD"
result = my_string.lower()  # O(n) — проходит через все 11 символов
print(result)  # "hello world"

Для каждого символа строки Python:

1. Проверяет, является ли символ прописной буквой
2. Если да, преобразует его в строчную букву
3. Если нет, оставляет как есть

Внутренняя реализация

Метод lower() — это встроенная функция, реализованная на C в ядре Python. Она работает примерно так:

# Концептуальная реализация на Python
def lower_concept(s):
    result = []
    for char in s:
        result.append(char.lower())  # Обработка каждого символа
    return ''.join(result)

# Это O(n) по времени и O(n) по памяти

Практический пример производительности

import time

# Строка длиной 1,000,000 символов
test_string = "HELLO WORLD " * 83334  # ~1MB

start = time.time()
result = test_string.lower()
end = time.time()

print(f"Время: {(end - start) * 1000:.2f}ms")
# На современном компьютере: ~1-5ms для миллиона символов

# Увеличиваем в 10 раз
test_string_large = test_string * 10
start = time.time()
result = test_string_large.lower()
end = time.time()
print(f"Время (10x больше): {(end - start) * 1000:.2f}ms")
# Время увеличится примерно в 10 раз

Сравнение с другими операциями

Операция O(1) — постоянное время:

my_string[0]  # Получение первого символа
len(my_string)  # Длина строки

Операция O(n) — линейное время:

my_string.lower()  # Каждый символ обрабатывается
my_string.upper()  # То же самое
my_string.capitalize()  # О(n)
my_string.replace('a', 'b')  # O(n)

Операция O(n²) — квадратичное время:

# Вложенные циклы
for char1 in my_string:
    for char2 in my_string:
        pass  # O(n²)

Важные уточнения

Строки неизменяемы — lower() создает новую строку, а не модифицирует исходную:

original = "HELLO"
lowercased = original.lower()
print(original)     # "HELLO" (не изменилась)
print(lowercased)   # "hello" (новая строка)

Память — дополнительно выделяется O(n) памяти для результирующей строки.

Оптимизация

Если вам нужно часто сравнивать строки без учета регистра, лучше преобразовать один раз:

# Плохо
if user_input.lower() == "hello":
    pass
if user_input.lower() == "hello":
    pass

# Хорошо
lower_input = user_input.lower()  # O(n) один раз
if lower_input == "hello":
    pass
if lower_input == "hello":  # O(1) сравнение
    pass

Вывод

string.lower() имеет сложность O(n) по времени и по памяти. Это неминуемо, так как нужно обработать каждый символ строки. Однако в абсолютных значениях эта операция очень быстра благодаря оптимизированной реализации на C внутри Python.