最坏情况分析

Question

Im学习算法的最坏情况分析

对于x> = 2，rand（x）是将1的值从1返回到x-1的函数，它们具有统一的概率$ \ frac {1} {x-1} $并且max（x，y）输出更大值和min（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时，假设rand（）返回1，则max（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但是如何找到最坏情况的顺序？

Answer 1

算法A：最坏的情况是X尽可能缓慢地减小。在循环体的一次迭代之后，X的最大可能值为X-1（因为rand可以返回最大值，并且由于Y为正，所以X-Y必须小于X）。因此，在最坏的情况下，rand总是选择X-1，该函数的运行时渐近地由线性函数-O（n）限制。

算法B：最坏的情况是X尽可能缓慢地减小。循环体重复一遍后，X的最大可能值为floor（X / 2）。原因如下：假定Y小于楼板（X / 2）。然后min将选择Y而不是X-Y。相反，假定Y大于floor（X / 2）。然后min将选择X-Y而不是Y。因此，当Y = floor（X / 2）时，将达到最坏的情况。如果我们让N = 2 ^ M，那么X将减半大约M倍。这意味着运行时是渐近对数的-O（log n）。

算法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值的表达式都是+ c（n-1）的形式。这是一个线性函数，因此我们希望该算法的运行时间是渐近线性的：O（n）。