Какова сложность этой функции?

Question

Я практикующий в Codeacademy, и я должен сделать следующую функцию:

Определим функцию под названием anti_vowel, которая принимает одну строку, текст, в качестве входных данных и возвращает текст со всеми гласными удалены

Эта это мое решение.

def anti_vowel(text): 
md = "" 
for ch in text: 
    if ch not in "aeiouAEIOU": 
     md = md + ch 
return md 

Это хорошо работает, но мне интересно, в чем сложность функции.

Я думаю, что это O(nk) где n: = "длина текста" и k: = "длина" aeoiuAEIOU "".
Я беру один элемент текста и сравниваю его со всеми гласными, что занимает время O (k). Но я повторяю это n раз, поэтому я делаю все это в O(nk). Правильно ли мой анализ? Как я мог улучшить свою функцию? Может ли он быть линейным?

Answer 1

Вы правы, сложность вашей функции O(nk). Что вы пропустили, так это то, что O(nk) равно O(n), если k - это постоянная, не равная нулю. Это означает, что ваша функция уже работает в линейном времени.

Вы повторяете строку text с цифрами n. На каждой итерации вы проверяете, находится ли текущий символ в строке исправлено длина k (k - постоянная!). В худшем случае эта проверка займет k шагов.

Таким образом, ваша сложность:

O(k)O(n) = O(kn) = O(n)

Я предлагаю вам прочитать об основных свойствах классов сложности, в частности, как их сумма, их произведение и умножение на постоянную работу here.

Answer 2

Сложность Big-O не работает. k (длина гласных) является константой, она не изменяется в зависимости от длины ввода. Поэтому мы уменьшаем его при расчете сложности.

Ваша функция - только O (n), т.е. линейная сложность.