问题描述
据我所知，大O符号的概念，它的东西在我自己我带来了最近学习。
I understand the concept of the Big O notation and its something i've brought upon myself to learn recently.
不过，说一个给定的算法，它递归调用自身直到作业完成后，如果有一个或我的return语句，这将如何影响大O符号？
But say for a given algorithm, which recursively calls itself until the job is complete, if there is an OR in my return statement, how will that effect the Big O notation?
这里的算法迄今：
**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？
Does having the or make it n^2?
推荐答案
这是远不如你的想法。如果该或需要两部分进行评估的时候有些％，那么你将结束与O（2 ^ n）的（而不是为O（n ^ 2））的递归调用。
It's far worse than you think. If both halves of the "or" will need to be evaluated some % of the time, then you will end up with O(2^n) (not O(n^2)) recursive calls.
比方说，它需要的两半或时间的10％。平均而言，你有你做两半才走下来10ish水平，所以你身边有：
Let's say it takes both halves of the OR 10% of the time. On average you have to go down 10ish levels before you do both halves, so you have around:
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），广告等）取O（n）的时间，而不是持续时间。
Also, it's worse than that again, because all those string manipulations (length(a+b), a-d, etc.) take O(n) time, not constant time.
编辑：我应该指出，O（2 ^ n）是不实际正确的。它的指数时代，但O（2 ^（N / 10））或任何严格小于O（2 ^ n）的较少。把它写一个正确的方法是2 ^ O（N）
I should mention that O(2^n) is not actually correct. It's "exponential time", but O(2^(n/10)) or whatever is strictly less than O(2^n). A correct way to write it is 2^O(n)
编辑：
有关此问题的一个很好的解决方案将使用动态规划。
A good solution for this problem would use dynamic programming.
让行（I，J）= true，如果c的第I + J字是的第i个字符和b的第j个字符的有序洗牌。
Let OK(i,j) = true if the first i+j characters of c are an ordered shuffle of the first i characters of a and the first j characters of b.
行（ⅰ，0）很容易计算对于所有的i。然后，你可以从确定计算所有的行（I，J）（I，J-1）。当你已经涵盖了所有与I + J =长度（C）的情况下，则返回true，如果其中任何一个是真实的。
OK(i,0) is easy to calculate for all i. Then you can calculate all the OK(i,j) from OK(i,j-1). When you've covered all the cases with i+j = length(c), then return true if any one of them is true.
这篇关于算法的运行时间复杂度递归BIG-O的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！