Как мне найти временную сложность T (n) и показать, что она жестко ограничена (Большая Тета)?

Question

Я пытаюсь выяснить, как обеспечить временную сложность в наихудшем случае.Я не уверен в своем анализе.Я прочитал вложенные for петли big O - это n^2;правильно ли это для for цикл с while петля внутри?

// A is an array of real numbers.
// The size of A is n. i,j are of type int, key is
// of type real. 
Procedure IS(A)    
for j = 2 to length[A]     
{                
   key = A[ j ]               
   i = j-1   
   while i>0 and A[i]>key    
   {       
      A[i+1] = A[i]                         
      i=i-1                    
   }                
   A[i+1] = key      
}

до сих пор у меня есть:

j=2 (+1 op)  

i>0 (+n ops)   
A[i] > key (+n ops)

so T(n) = 2n+1?  

Но я не уверен, должен ли я заходить внутрь while и for циклы для анализа временной сложности в худшем случае...

Теперь я должен доказать, что это тесно связано, это Большая тета.

Я читал, что вложенный for циклы имеют Большое О из n^2.Верно ли это также для Большой Теты?Если нет, то как бы я занялся поиском Большой Теты ?!

**C1= C sub 1, C2= C sub 2 и no = n ничего - все это элементы положительных вещественных чисел

Чтобы найти T(n) Я посмотрел на значения j и посмотрел, сколько раз выполнялся цикл while:

values of J:   2, 3, 4, ... n  
Loop executes: 1, 2, 3, ... n

Анализ:
Возьмите суммирование выполнений цикла while и признайте, что это (n(n+1))/2 Я назначу это своим T(n) и докажите, что она жестко ограничена n^2.Это n(n+1)/2= θ(n^2)

Работа с нуля:

Find C1, C2, no є R+ such that 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2)for all n ≥ no

To make 0 ≤ C1(n) true, C1, no, can be any positive reals   
To make C1(n^2) ≤ (n(n+1))/2, C1 must be ≤ 1  
To make (n(n+1))/2 ≤ C2(n^2), C2 must be ≥ 1  

ПФ:

Find C1, C2, no є R+ such that 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2) for all n ≥ no
Let C1= 1/2, C2= 1 and no = 1.  

1. покажите, что 0 ≤ C1 (n ^ 2) истинно C1 (n ^ 2) = n ^ 2/2
   n ^ 2/2≥ нет ^ 2/2
   ⇒нет^2/2≥ 0
   1/2 > 0
   Следовательно, C1 (n ^ 2) ≥ 0 доказано, что это правда!

2. покажите, что C1 (n ^ 2) ≤ (n (n + 1))/2 истинно C1 (n ^ 2) ≤ (n (n + 1))/2
   n ^ 2/2 ≤ (n (n + 1))/2 n ^ 2 ≤ n (n + 1)
   n ^ 2 ≤ n ^ 2+ n
   0 ≤ n

   Мы знаем, что это верно, поскольку n ≥ no = 1
   Следовательно, C1(n ^ 2) ≤ (n (n + 1))/2 доказано, что это правда!

3. Покажите, что (n (n + 1))/2 ≤ C2(n ^ 2) истинно (n (n + 1))/2 ≤ C2(n ^ 2)
   (n+1)/2 ≤ C2(n)
   n+1 ≤ 2 C2(n)
   n+1 ≤ 2(n)
   1 ≤ 2n-n
   1 ≤ n (2-1) = n
   1≤ n
   Кроме того, мы знаем, что это верно, поскольку n ≥ no = 1

   Следовательно, по 1, 2 и 3, θ(n ^ 2 )= (n (n+1))/2 верно, поскольку
   0 ≤ C1(n ^ 2) ≤ (n(n + 1))/2 ≤ C2(n ^ 2) для всех n ≥ no

Скажите мне, что вам нравится, ребята...Я пытаюсь разобраться в этом материале и хотел бы, чтобы вы внесли свой вклад!

Answer 1

Вы, кажется, реализуете алгоритм сортировки при вставке, который , как утверждает Википедия , равен O(N²).

Как правило, вы разбиваете компоненты на основе вашей переменной N, а не вашей постоянной C, когда имеете дело с Big-O.В вашем случае все, что вам нужно сделать, это посмотреть на циклы.

Ваши два цикла - это (худшие случаи):

for j=2 to length[A]
    i=j-1
    while i > 0
        /*action*/
        i=i-1

Внешним циклом является O(N), поскольку он напрямую связан с количеством элементов.

Обратите внимание, как ваш внутренний цикл зависит от хода выполнения внешнего цикла.Это означает, что (игнорируя отдельные проблемы) внутренний и внешний циклы связаны следующим образом:

 j's     inner
value    loops
-----    -----
  2        1
  3        2
  4        3
  N       N-1
-----    -----
total    (N-1)*N/2

Таким образом, общее количество раз, когда /*action*/ встречается is (N² - N)/2, что равно O(N²).

Answer 2

Смотреть на количество вложенных циклов - не лучший способ получить решение.Лучше посмотреть на "работу", которая выполняется в коде под большой нагрузкой N.Например,

for(int i = 0; i < a.size(); i++)
{
  for(int j = 0; j < a.size(); j++)
  {
    // Do stuff
    i++;
  }
}

является O(N).

Функция f находится в Big-Theta из g, если она одновременно находится в Big-Oh из g и Big-Omega из g.Наихудший случай происходит, когда данные A представляют собой монотонно убывающую функцию.Затем, для каждой итерации внешнего цикла, выполняется цикл while.Если бы каждый оператор давал значение времени, равное 1, то общее время было бы равно 5 * (1 + 2 + ...+ n - 2) = 5*(n - 2)*(n - 1) / 2.Это дает квадратичную зависимость от данных.Однако, если данные A представляют собой монотонно возрастающую последовательность, условие A[i] > key всегда будет выполняться с ошибкой.Таким образом, внешний цикл выполняется за постоянное время, N - 3 раза.Тогда наилучший случай f имеет линейную зависимость от данных.Для среднего случая мы берем следующее число в A и находим его место в ранее выполненной сортировке.В среднем это число будет находиться в середине этого диапазона, что подразумевает, что внутренний цикл while будет выполняться вдвое реже, чем в худшем случае, что дает квадратичную зависимость от данных.

Answer 3

Большое О (в основном) о том, сколько раз элементы в вашем цикле будут просмотрены для выполнения задачи.

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

Причина, по которой цикл внутри цикла равен O (n ^ 2), заключается в том, что каждый элемент в цикле должен повторяться сам по себе ^ 2 раза.Изменение типа цикла не имеет к этому никакого отношения, поскольку по сути речь идет о количестве итераций.

Существуют подходы к алгоритмам, которые позволят вам сократить количество необходимых вам итераций.Примером этого являются "разделяй и властвуй" алгоритмы , подобные Быстрая Сортировка, который, если я правильно помню, равен O(nlog(n)).

Трудно придумать лучшую альтернативу вашему примеру, не зная более конкретно, чего вы пытаетесь достичь.