如何通过下面的代码使用if-else语句进行复杂度分析？

Question

我试图找出这段代码的复杂性：

///Note: a[i] is an array with n elements

for (int i = 0; i < n; i++) {
  if (Math.random() > 0.25)
       if (i%4 == 0)
        BubbleSort (a[i]);
       else
        QuickSort (a[i]);
  else
   for (int j = i; j < n; j++)
     for (int k = i; k < n; k++)
       BinarySearch (a[i]);
}

根据我的理解，BubbleSort为n^2，QuickSort最佳情况为nlogn，但最差情况为n^2，BinarySearch为logn，但需要对列表进行排序。

在两次执行二进制搜索时，遍历代码25％，而在本节中，两次执行QuickSort或BubbleSort。

[它将有1/4的机会进行BubbleSort，有3/4的机会进行QuickSort。

要发现复杂性，我是否需要为最佳情况和最坏情况分别制定方程式？

Answer 1

由于复杂度是功能类别而不是函数本身，因此您可以计算所有分支方案的复杂度并考虑最坏的情况。

[为了说明，让我们考虑您有75％的复杂度是O（n）[最佳方案]，有25％的复杂度是O（n ^ 2）[最坏方案]。您可以这样想：

0.75 * O(n) + 0.25 * O(n^2)
0.75 * c1 * n + 0.25 * c2 * n^2
c3 * n + c4 * n^2    (c3 = 0.75 c1 , c4 = 0.25 c2)

但是c3 * n + c4 n^2在O（n ^ 2）类之内