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

Question

Я пытаюсь выяснить, как дать сложность времени наихудшего случая. Я не уверен в моем анализе. Я прочитал вложенные циклы for, большие O is 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 имеют значение Big O 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  

PF:

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 ≥ нет

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

Answer 1

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

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

Ваши две петли (в худшем случае):

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*/, равно (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 находится в биг-тета g, если она есть и в биг-ом g, и в биг-омеге 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 (в основном) о том, сколько раз элементы в вашем цикле будут просматриваться для выполнения задачи.

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

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

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

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