Анализ временной сложности наивного Цезаря Сайфера

Question

Я начал делать практические задачи для собеседования, и когда я решал «Цезаря Сайфера», наивное решение, которое я нашел на первый взгляд, было примерно таким:

def caesarCipherEncryptor(string, key): 
    abc = 'abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz'
    key = key % 26

    letter = 0
    result = ''

    for char in string:
        index = abc.find(char)
        result += abc[index + key]

    return result

Мое понимание сложности времени все еще очень basi c.

Мой вопрос ... Основной кусок моего наивного решения сосредоточен на функции поиска, которая является o (n) в строке: ab c Я прошел. Поскольку он выполняет o (n) операций над каждым символом для строки, которую нужно зашифровать, это означает, что это o (n ^ 2). Я также думал, что вся операция - просто o (n) из-за однопроходной природы решения, связанного с мнением, что операция find (char) является константой в худшем случае, находя индекс как 'z' (25-й индекс). Должен ли мой анализ сложности времени быть чисто в перспективе входной строки?

Answer 1

пусть длина данной строки равна n. (всегда объясните, что означает n!)

Ваш алгоритм перебирает каждый символ 'строки' и для каждого из них:

выполняет поиск в массиве 26 размеров

execute одна простая математическая операция.

Таким образом, временная сложность вашего алгоритма равна n (26 + 1)

. Асимптотически можно сказать, что ваш алгоритм равен O (n) и даже Theta (n). )

Проделав небольшую работу, вы можете показать, что любой правильный алгоритм, решающий проблему, выполняет по крайней мере n операций, таким образом, асимптотически ваш алгоритм настолько эффективен, насколько это возможно. (другими словами, эта проблема - Омега (н))