Наихудшая Сложность Времени для алгоритма

Question

Какова временная сложность наихудшего случая t (n): - Я читаю эту книгу об алгоритмах и в качестве примера как получить T (n) для .... как алгоритм выбора Sort

---

Например, если я имею дело с selectionSort (A [0..n-1])

//sorts a given array by selection sort
//input: An array A[0..n - 1] of orderable elements.
//output: Array A[0..n-1] sorted in ascending order

позвольте мне написать псевдокод

for i <----0 to n-2 do
  min<--i
for j<--i+1 to n-1 do
   ifA[j]<A[min] min <--j
swap A[i] and A[min]

-------- Я тоже напишу это на C # ---------------

private int[] a = new int[100];

// number of elements in array
private int x;

// Selection Sort Algorithm
public void sortArray()
{
  int i, j;
  int min, temp;

  for( i = 0; i < x-1; i++ )
  {
    min = i;

    for( j = i+1; j < x; j++ )
    {
      if( a[j] < a[min] )
      {
        min = j;
      }
    }

    temp = a[i];
    a[i] = a[min];
    a[min] = temp;
  }
}

==================

Теперь, как получить t (n) или, как известно, сложность времени наихудшего случая

Answer 1

Это было бы O (n ^ 2).

Причина в том, что у вас есть один цикл for, вложенный в другой цикл for. Время выполнения внутреннего цикла for O (n) происходит для каждой итерации внешнего цикла for, который снова равен O (n). Причина каждого из них в отдельности - O (n), потому что они занимают линейное количество времени, учитывая размер ввода. Чем больше вход, тем больше времени занимает линейная шкала, n.

Чтобы решить математику, которая в данном случае тривиальна, просто умножьте сложность внутреннего цикла на сложность внешнего цикла. n * n = n ^ 2. Потому что помните, что для каждого n во внешнем цикле вы должны снова сделать n для внутреннего. Для уточнения: n раз для каждого n.

O (n * n).

O (N ^ 2)

Answer 2

Кстати, вы не должны смешивать сложность (обозначается как big-O) и функцию T. Функция T - это количество шагов, которые алгоритм должен пройти для данного входа.

Итак, значение T (n) - это фактическое количество шагов, тогда как O (что-то) обозначает сложность. Под обычным злоупотреблением обозначениями T (n) = O (f (n)) означает, что функция T (n) имеет не более той же сложности, что и другая функция f (n), которая обычно будет самой простой из возможных функций. класса его сложности.

Это полезно, потому что позволяет нам сфокусироваться на общей картине: теперь мы можем легко сравнить два алгоритма, которые могут иметь очень разные функции T (n), посмотрев, как они работают «в долгосрочной перспективе».

Answer 3

Еще одно воспоминание о докторантуре.

Во-первых, функция T - это просто количество времени (обычно в некотором количестве шагов , о котором подробнее ниже), которое алгоритм использует для выполнения задачи. Что такое «шаг», в некоторой степени определяется использованием; например, обычно принято считать количество сравнений в алгоритмах сортировки, но количество элементов, ищущих в алгоритмах поиска.

Когда мы говорим о времени наихудшего случая алгоритма, мы обычно выражаем это с помощью нотации big-O. Так, например, вы слышите, что сортировка пузырьков занимает время O (n & sup2;). Когда мы используем большие обозначения O, мы на самом деле говорим, что рост некоторой функции - в данном случае T - не быстрее, чем рост некоторой другой функции, умноженной на постоянную. Это

T (n) = O (n & sup2;)

означает для любого n , независимо от его размера, существует константа k , для которой T (n) ≤ kn & sup2; . Точка некоторого замешательства здесь заключается в том, что мы используем знак «=» в перегруженном виде: это не означает, что оба значения равны равны в числовом смысле, просто мы говорим, что T (n) ограничено kn & sup2; .

В примере из вашего расширенного вопроса похоже, что они подсчитывают количество сравнений в цикле for и в тесте; это помогло бы увидеть контекст и вопрос, на который они отвечают. В любом случае, тем не менее, это показывает, почему нам нравится нотация big-O: W (n) здесь O (n) . (Доказательство: существует константа k, а именно 5, для которой W (n) ≤ k (3n) +2. Это следует из определения O (n) .)

Если вы хотите узнать больше об этом, обратитесь к любому хорошему тексту алгоритмов, например, Введение в алгоритмы , по Cormen и др.

Answer 4

@ Сара Джонс Набор слайдов, на который вы ссылались - и алгоритм в нем

Сложность измеряется для каждой примитивной / атомарной операции в цикле for

for(j=0 ; j<n ; j++)
{
    //...    
}

Слайды оценивают этот цикл как 2n + 2 по следующим причинам:

Начальный набор j = 0 (+1 оп) Сравнение j Приращение j ++ (n ops) Окончательное условие для проверки, если j

Во-вторых, сравнение внутри цикла for

if(STudID == A[j])      
    return true;

Это оценивается как n ops. Таким образом, результат, если сложить +1 op, n ops, n ops, +1 op, n ops = 3n + 2 сложности. Так что T (n) = 3n + 2

Признайте, что T (n) не совпадает с O (n).

Answer 5

3n + 2 - правильный ответ в отношении цикла. На каждом шаге цикла выполняются 3 атомарных операции. На самом деле j ++ - это две операции, а не одна. и J

Answer 6

писать псевдокоды для поиска, вставки и удаления информации об ученике из хеш-таблицы. рассчитать время лучших и худших случаев сложности