算法运行时复杂度递归 BIG-O

Question

我了解 Big O 表示法的概念以及我最近自发学习的东西。

但是对于一个给定的算法来说，它会递归调用自身直到作业完成，如果我的 return 语句中有一个 OR，这将如何影响大 O 表示法？

到目前为止的算法是:

**Algorithm: orderedSort(a,b,c)**
given strings a,b,c determine whether c is an ordered shuffle of a and b

l := length of (a + b)
if (l = 0) then
    return true
if (l not = length of c)
    return false
else
    d := substring of a position 1 to 1
    e := substring of b position 1 to 1
    f := substring of c position 1 to 1
if (d = f) then 
    return orderedSort(a-d, b, c-f) 
if (e = f) then
    return orderedSort(a, b-e, c-f)
if (d and e = f) then
    return orderedSort(a-d, b, c-f) or orderedSort(a, b-e, c-f)

是否有或使它成为 n^2？

Answer 1

远比你想象的要糟糕。如果“或”的两半都需要在某些时间进行评估，那么您最终将得到 O(2^n)(而不是 O(n^2))次递归调用。

假设它花费了一半或 10% 的时间。平均而言，在完成两个半程之前，你必须降低 10 左右的水平，所以你有:

1 call with length n
2 calls with length n-10
4 calls with length n-20
8 calls with length n-30
...
2^(n/10) calls with length 0

此外，它又比那更糟，因为所有这些字符串操作(长度 (a+b)、a-d 等)都需要 O(n) 时间，而不是常数时间。

编辑:我应该提到 O(2^n) 实际上并不正确。这是“指数时间”，但是 O(2^(n/10)) 或任何严格小于 O(2^n) 的东西。正确的写法是 2^O(n)

编辑:

这个问题的一个很好的解决方案是使用动态规划。

如果 c 的前 i+j 个字符是 a 的前 i 个字符和 b 的前 j 个字符的有序混洗，则令 OK(i,j) = true。

OK(i,0) 很容易计算所有 i。然后你可以从 OK(i,j-1) 计算出所有的 OK(i,j)。当您用 i+j = length(c) 涵盖了所有情况后，如果其中任何一个为真，则返回真。