В чем суть этого наивного решения?

Question

Вот простая функция, которая принимает две входные строки. Он возвращает True, если вторая строка является анаграммой первой.

def validAnagram(str1, str2):
    if len(str1) != len(str2):
        return False

    str1_arr = [char for char in str1]
    str2_arr = [char for char in str2]

    for char in str1_arr:
        if char in str2_arr:
            str2_arr.remove(char)
        else:
            return False
    return True

Я учусь вычислять Большое О программ, которые я пишу. Время выполнения этой функции: O (N ² ) или O (N ³ )?

Я предполагаю, что это O (N ³ ), потому что Условие «если» также выполняется O (N). Итак, его 3 вложенные операции O (N), в результате чего время выполнения составляет O (N ³ ). Пожалуйста, поправьте меня, если я ошибаюсь.

Answer 1

Это O(N^2). У вас есть O(N) итераций, в которых вы выполняете операцию O(N). Это приводит к O(N^2) сложности в целом.

Я думаю, что вы ошиблись, вычисляя эту часть как O(N^2), хотя на самом деле это O(N):

    if char in str2_arr:
        str2_arr.remove(char)

, потому что у вас есть O(N) + O(N) здесь, что по-прежнему просто O(N).