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

Question

Я пытаюсь выяснить, как дать худшую временную сложность. Я не уверен в моем анализе. Я читал вложенные for петли большие 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 петли имеют Big O of n^2. Это также верно для Большой Теты? Если не так, как я могу найти Большую Тету ?!

** С1 = С 1 к югу, С2 = С 2 югу, и нет = п нет все элементы положительных действительных чисел

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

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

Анализ:
Возьмите суммирование расстрелах в то время как петли и признать, что это (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 ≤ С1 (п^2) истинно С1 (п^2) = n^2/2
   n^2/2≥ no^2/2
   ⇒no^2/2≥ 0
   1/2> 0
   Следовательно, C1 (n^2) ≥ 0 доказано!

2. показывают, что С1 (п^2) ≤ (п (п + 1))/2 истинно С1 (п^2) ≤ (п (п + 1))/2
   п^2/2 ≤ (п (п + 1))/2 п^2 ≤ п (п + 1)
   п^2 ≤ п^2 + п
   0 ≤ п

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

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

   Следовательно, на 1, 2 и 3, Q (N^2) = (п (п + 1))/2 верна с
   0 ≤ C1 (п^2) ≤ (N (N + 1))/2 ≤ C2 (п^2) для всех п^не

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

Answer 1

Вы, кажется, реализации insertion sort algorithm, что Википедия утверждает, что это O (N 2 ).

Как правило, вы разбиваете компоненты, основанные на вашей переменной 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*/ встречается (п - N)/2 , который представляет собой O (N).

Answer 2

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

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

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

Существуют подходы к алгоритмам, которые позволят вам сократить количество итераций, в которых вы нуждаетесь. Примером этого являются «divide & conquer» алгоритмы, такие как Quicksort, что, если я правильно помню, это O (nlog (n)).

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

Answer 3

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