递归函数中嵌套循环的时间复杂度是多少？

Question

我有一个嵌套的递归函数 loop.I正在寻找时间复杂度是多少？这是函数

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)

Answer 1

假设n是input_str的长度。该算法在最坏情况下可以递归迭代 n 次，即在每次递归调用中 letter 将增加 1，并且可以一直持续到 n。在每次迭代中，最坏的情况是 O(n)（运行 循环完全）。因此，时间复杂度为O(n^2).