Как выполнить анализ сложности из приведенного ниже кода с помощью операторов if-else? - PullRequest
Новая
       23

Как выполнить анализ сложности из приведенного ниже кода с помощью операторов if-else?

0 голосов
/ 02 февраля 2020

Я пытаюсь выяснить, в чем сложность этого кода: 

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

Чтобы найти сложность, я должен был бы составить отдельные уравнения для лучшего и наихудшего случая?

1 Ответ

1 голос
/ 03 февраля 2020

Поскольку сложность - это класс функций , а не сама функция, вы можете рассчитать сложность для всех ваших сценариев ветвей ios и рассмотреть наихудший случай.

Просто для иллюстрации, давайте рассмотрим, что у вас 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)

...