Какова функция стоимости следующего алгоритма?

Question

input : arr[n]
output : median value of arr

for i = 0 ... n/2
  for j = 0 ... i
      if arr[j] > arr[n-i-1]
         temp = arr[j]
         arr[j] = arr[n-i-1]
         arr[n-i-1] = temp

Я знаю, что сложность алгоритма составляет O (n ^ 2). Я не смог найти конкретное c определение функции стоимости. Должен ли я включать сравнения в l oop и утверждение if как затраты? Было бы полезно, если бы кто-то мог определить, что такое функция стоимости, и помочь мне понять и решить эту проблему.

Answer 1

Вы должны учитывать количество сравнений в циклах for и в операторе if и количество раз, сколько for циклов запускается

Answer 2

Да, сравнения должны быть включены в стоимость. Существует около n^2/8 сравнений, которые дают квадратичную c сложность.

Обратите внимание, что вы не знаете реального числа перестановок, но этот факт не влияет на сложность. Количество операций варьируется от n^2/8 до 4*n^2/8, но оба выражения относятся к Theta(n^2) классу

Точный расчет стоимости зависит от вашего подхода к книге и желания инструктора :).

В общем случае необходимо рассчитать все операторы со стоимостью 1 (несмотря на то, что некоторые из них могут быть внутренне сложными, например, for-l oop). Например, for i = 0 ... n/2 дает стоимость n/2, оба for j = 0 ... i и if arr[j] > arr[n-i-1] дают стоимость k=n/2*(n/2-1)/2, а свопы дают стоимость в диапазоне k..3k

Таким образом, общая стоимость составляет

n/2 + 2 * n/2*(n/2-1)/2 + x * n/2*(n/2-1)/2

где x зависит от данных и лежит в диапазоне 1..3