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

Question

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

---

Например, если я имею дело с 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

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

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

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

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

Начальный набор j=0 (+1 op)

Сравнение j < n (n операций)

Приращение j++ (n операций)

Последнее условие для проверки, является ли j < n (+1 операция)

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

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

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

Признайте, что T (n) - это не то же самое, что O (n).

Answer 2

Это было бы 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 3

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

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

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

Answer 4

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

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

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

T (n) = O(n2)

средства для любого n, независимо от того, насколько велика, существует постоянная k для чего T(n) ≤ kn2.Некоторая путаница здесь заключается в том, что мы используем знак "=" перегруженным образом:это не значит, что эти двое равный в числовом смысле, просто то, что мы говорим, что T(n) является ограниченный kn2.

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

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

Answer 5

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

Answer 6

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