Блог

У меня есть рекурсивная функция с вложенным циклом.Я ищу, какова временная сложность? Вот функция

 def csFirstUniqueChar(input_str,letter = 0,num = 1):
    if letter == len(input_str):
        return -1
    for x in range(len(input_str)): 
        if x == letter:
            continue
        if input_str[x] == input_str[letter]:
            num  = 1
    if num == 1:
            return letter
    else:
        return csFirstUniqueChar(input_str,letter   1,1)
  

Предположим n , это длина input_str . В худшем случае алгоритм может повторять n время рекурсивно, т. Е. При каждом рекурсивном вызове letter будет увеличиваться на 1 , и его можно продолжить до n . На каждой итерации хуже всего O(n) (выполнение цикла полностью). Следовательно, временная сложность O(n^2) .