Временная сложность для вложенных циклов в Python - PullRequest
Новая
       26

Временная сложность для вложенных циклов в Python

0 голосов
/ 13 октября 2019

У меня есть следующий код, который проверяет, содержит ли строка s две первые буквы конкретного слова (в нижнем регистре и в любом порядке): 

def check_letters(input_string):

    word = 'Hello' # 1
    array_size = len(input_string) # 1

    for i in range (0, array_size): # n
        if input_string[i].lower()==word[0].lower(): # n
            for j in range (0, array_size): # n^2
                if input_string[j].lower()==word[1].lower(): # n^2
                    return True # 1

    return False # 1

Я прокомментировал сложностькаждая строка, и кажется, что сложность моей функции в худшем случае равна O (N ^ 2), поскольку вложенный цикл имеет сложность O (N ^ 2). Являются ли сложности каждой строки правильными и является ли сложность наихудшего случая O (N ^ 2)? Кроме того, является ли размер ввода только длиной строки?

...