对代码的大 O 表示法感到困惑

Question

我试图在不使用任何辅助排序函数和嵌套循环的情况下查找给定的字符串是否是变位词。

因此我尝试使用 while 循环；但是，我不确定这段代码的大 O 表示法是什么。你能帮忙吗？

def anagrams(string1, string2):
    if len(string1) != len(string2):
        return False
    string3 = ""
    x = 0
    y = 0
    while x < len(string1) and y < len(string2):
        element = string1[x]
        if element == string2[y]:
            string3 += element
            x += 1
            y = 0
        else:
            y += 1
    return string1 == string3

Answer 1

我相信它会是 O(n^2)，因为你的 x 值趋于增加，但你的 y 值可以继续重置为零，因此并不比嵌套循环好。

Answer 2

我会尝试提供一个明确的例子。

首先，假设 string1 = 'ABC' 和 string2 = 'DE'.
len(string1) = 3, len(string2) = 2
我们先比较string1[0]和string2[0]，不一样，y++;
我们第二次比较string1[0]和string2[1]，不一样，y++;
跳出循环； returns false

其次，假设 string1 = 'ABC' 和 string2 = 'AC'
我们先比较string1[0]和string2[0]，一样的，x++； string3 += string1[0]
我们第二次比较string1[1]和string2[1]，不一样，y++;
跳出循环，returns false

第三，假设 string1 = 'AB' 和 string2 = 'AB'
我们先比较string1[0]和string2[0]，一样的，x++；字符串 3 += 字符串 1[0] string3 = 'A'
我们第二次比较string1[1]和string2[0]，不一样，y++;
我们第三次比较string1[1]和string2[1]，一样，x++； string3 += string1[1] string3 = 'AB'
;我们知道它会 return true

因此，O(n+m)，给定 n = len(string1)，m = len(string2)。谢谢

Answer 3

该代码在运行时为 O(N^2)，但不正确。

代码等同于：

def anagrams(s1, s2):
    if len(s1) != len(s2): return False
    r = ''
    for s in s1:
        if s in s2: r += s
    return r == s1

这样写，显然是O(N^2)。

这会检查 s1 中的每个字符是否也在 s2 中，但这不足以检测变位词：您还必须检查每个字符的计数是否正确。

下面是算法正确性的反例："abba"和"barf"。

对代码的大 O 表示法感到困惑

Confused about the big O notation of the code

python

big-o