最坏情况分析

Question

我正在学习算法的最坏情况分析

对于x>=2，rand(x)是return1个值从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() return 1 ，然后 max(1,x-1) 所以最坏的情况将是 O(n)

对于算法 B，当 x =10 时，假设 rand() return 4 来自 10 ，它将调用 min(4,10-4) ，将再次调用 x=4 等，但最坏的情况会是 x/2 或 (x-1)/2

对于算法 C

它是递归的(?)，比如x =10 and y=rand(x)=4，当它调用Fn(4)和Fn(10-4=6)时，它会再次调用，再次直到小于 2 但是我怎样才能找到最坏情况的顺序呢？

Answer 1

算法 A：最坏的情况发生在 X 尽可能慢地减小时。循环体的一次迭代后 X 的最大可能值为 X - 1（因为这是最大值 rand can return，并且由于 Y 为正，因此 X - Y 必须小于 X）。因此，在 rand 总是 selects X - 1 的最坏情况下，该函数的运行时间渐近地受线性函数的限制 - O(n).

算法 B：最坏的情况发生在 X 尽可能慢地减小时。循环体一次迭代后 X 的最大可能值为 floor(X / 2)。原因如下：假设 Y 小于 floor(X / 2)。然后 min 将 select Y 而不是 X - Y。假设 Y 大于 floor(X / 2)。那么 min 将 select 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) 的前几个值的右边 selection:

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).

最坏情况分析

worst case analysis

algorithm

complexity-theory

pseudocode

time-complexity