如何使用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％的时间将执行二进制搜索，其他时间将进行快速排序或冒泡排序，在该部分中，它将有1/4的机会进行冒泡排序，而有3/4的机会进行冒泡排序快速排序。为了找到复杂性，我必须为最佳情况和最坏情况分别制定方程式？

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）类之内