最坏情况分析
学习算法的最坏情况分析
对于x>=2，rand(x)是将1值从1返回到x-1的函数，该函数具有一致概率$\frac{1}{x-1 }$和max(x，y)输出更大的值和最小(x，y)输出较小的值，我需要找到每种算法的最坏情况复杂性。
Algorithm A
Input=n
x=n
WHILE x>=2
y=rand(x)
x=max(y,x-y)
ALGORITHM B
Input =n
x=n
While x>=2
y=rand(x)
X=min(y,x-y)
ALGORITHM C
Input : value n (integer)
void fn(x :int)
if(x>=2)
y=rand(x)
Fn(y)
Fn(x-y)
Else
Return
fn(n)对于算法A，当x=10返回1，则最大(1，x-1)时，最坏的情况是O(n)
对于算法B，当x =10时，假设rand()从10返回4，它将调用min(4,10-4)，再次调用x=4等，但最坏的情况是x/2或(x-1)/2。
算法C
它是递归的(？)，例如，如果x =10，y=rand(x)=4，当它调用Fn(4)和Fn(10-4=6)时，它将一次又一次地循环，直到小于2，但是如何找到最坏情况的顺序？
回答 1
Stack Overflow用户
发布于 2020-01-14 13:36:20
算法A:最坏的情况发生在X越慢越慢的时候。循环体一次迭代后，X的最大可能值是X-1(因为这是rand可以返回的最大值，而且由于Y是正的，所以X必须小于X)。因此，在rand总是选择X-1的最坏情况下，函数具有由线性函数- O(n)渐近有界的运行时。
算法B:最坏的情况发生在X越慢越慢的时候。循环体一次迭代后，X的最大可能值是地板(X/ 2)。原因如下:假设Y小于下限(X/ 2)。然后min会选择Y而不是X，相反，假设Y大于地板(X/ 2)。因此，当Y =地板(X/ 2)时达到最坏的情况。如果N= 2^M，则X将在M次左右减半。这意味着运行时是渐近对数- O(log )。
算法C:我们可以将运行时的递归关系写下来如下：
T(0) = a
T(1) = b
T(n) = T(f(n)) + T(n-f(n)) + c我们需要找到函数f(n)，使递归尽可能坏。让我们开始检查n= 2，3，…，k，…看看是否出现了任何模式，这些模式可以告诉我们对f(N)的前几个值的正确选择：
T(2) has only one split: Y=1, X-Y=1; so T(2) = 2a + c
T(3) has two equivalent splits: Y=1, X-Y=2; so T(3) = 3a + 2c
T(4) has two different splits:
Y=1, X-Y=3: 4a + 3c
Y=2, X-Y=2: 4a + 3c
these end up being the same
T(5) has two different splits:
Y=1, X-Y=4: 5a + 4c
Y=2, X-Y=3: 5a + 4c
these end up being the same
T(6) has three different splits:
Y=1, X-Y=5: 6a + 5c
Y=2, X-Y=4: 6a + 5c
Y=3, X-Y=3: 6a + 5c
these end up being the same事实证明，所有这些都是完全相同的；其中的选择似乎根本不重要。这可能是因为每一步的额外工作量都是恒定的；如果它依赖于n，那么分析结果可能会有所不同。我们所看到的n的每个值的表达式都是an + c(n-1)形式。这是一个线性函数，所以我们期望这个算法的运行时是渐近线性的: O(n)。
https://stackoverflow.com/questions/59733215
复制相似问题
腾讯云开发者
