Como faço para encontrar a complexidade de tempo T (n) e mostrar que é rigidamente delimitada (Big Theta)?

Question

Eu estou tentando descobrir como dar um pior complexidade de tempo caso. Eu não tenho certeza sobre a minha análise. for aninhada eu li laços grande S é n^2; isto é correto para um loop for com um loop interno 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      
}

até agora eu tenho:

j=2 (+1 op)  

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

so T(n) = 2n+1?  

Mas eu não tenho certeza se eu tiver que ir para dentro dos laços while e for para analisar um tempo pior caso complexidade ...

Agora eu tenho que provar que está fortemente ligada, isto é Big theta.

Eu li que laços for aninhadas têm Big O de n^2. É este também é verdadeiro para Big Theta? Se não for como eu iria sobre encontrar Big Theta?!

** C1 = C sub 1, C2 = C sub 2, e não = n nada todos são elementos de números reais positivos

Para encontrar o T(n) Olhei para os valores de j e olhou para quantas vezes o loop while executado:

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

Análise:
Tome o somatório das execuções loop while e reconhecer que é (n(n+1))/2 Vou atribuir isso como meu T(n) e provar que está bem delimitada por n^2. Isso é n(n+1)/2= θ(n^2)

Risco Trabalho:

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. mostra que 0 = C1 (n ^ 2) é verdadeira C1 (n ^ 2) = n ^ 2/2 | n ^ 2 / 2= não ^ 2/2 | ?no ^ 2 / 2= 0
   1/2> 0
   Portanto C1 (n ^ 2) = 0 é comprovada verdade!

2. mostram que C1 (n ^ 2) = (n (n + 1)) / 2 é verdadeiro 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

   Esta sabemos é verdadeiro desde que n = não = 1 | Portanto C1 (n ^ 2) = (n (n + 1)) / 2 é comprovada verdadeiro!

3. Mostra que (n (n + 1)) / 2 = C2 (n ^ 2) é verdadeira (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
   Além disso, sabemos que isso é verdade desde n = não = 1

   Daí por 1, 2 e 3, ? (n ^ 2) = (n (n + 1)) / 2 é verdadeiro desde
   0 = C1 (n ^ 2) = (n (n + 1)) / 2 = C2 (n ^ 2) para todos os n = nenhuma

Diga-me o que você coisa caras ... Eu estou tentando entender este material e gostaria y'alls entrada!

Answer 1

Você parece estar implementando o ordenação por inserção algoritmo , que Wikipedia reivindicações é O (N ² ).

Geralmente, você quebrar componentes baseados fora sua variável N ao invés de seu constante C ao lidar com Big-O. No seu caso, tudo que você precisa fazer é olhar para os loops.

Seus dois loops são (piores casos):

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

O loop externo é S (N), uma vez que se relaciona directamente com o número de elementos.

Observe como o seu circuito interno depende do progresso do ciclo exterior. Isso significa que (ignorando off-by-one questões) os laços internos e externos estão relacionados da seguinte forma:

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

Assim, o número total de vezes que /*action*/ for encontrado é (N ² - N). / 2, que é O (N ² )

Answer 2

Olhando para o número de loops aninhados não é a melhor maneira de ir sobre a obtenção de uma solução. É melhor olhar para o "trabalho" que está sendo feito no código, sob uma carga pesada N. Por exemplo,

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

é O (N).

Uma função f está em Big-Theta de g se for tanto em Big-Oh de g e Big-Omega de g. O pior caso ocorre quando os dados de A é monotonicamente decrescente função. Então, para cada iteração do loop externo, as executa loop while. Se cada declaração contribuiu com um valor de tempo de 1, então o tempo total seria de 5 * (1 + 2 + ... + n - 2) = 5 * (n - 2) * (n - 1) / 2. Isto dá uma dependência quadrática na dados. No entanto, se os dados A é uma sequência monótona crescente, a condição A [i]> tecla sempre falhará. Assim, os executa loop externo em tempo constante, N - 3 vezes. O melhor caso de f, então, tem uma dependência linear sobre os dados. Para o caso médio, tomamos o próximo número em A e encontrar o seu lugar na classificação que ocorreu anteriormente. Em média, este número será no meio desta faixa, o que implica o loop while interno será executado metade tão frequentemente como no pior dos casos, dando uma dependência quadrática na dados.

Answer 3

Big O (basicamente) sobre quantas vezes os elementos do seu ciclo vai ser olhado, a fim de completar uma tarefa.

Por exemplo, uma O (n) algoritmo irá iterar através de cada elemento apenas uma vez. A O (1) algoritmo não terá para percorrer cada elemento em tudo, ele vai saber exatamente onde na matriz de olhar porque tem um índice. Um exemplo disto é uma tabela de matriz ou de hash.

A razão de um loop interno de um loop é O (n ^ 2) é porque cada elemento no circuito tem de ser iterada si ^ 2 vezes. A alteração do tipo do circuito não tem nada a ver com isso, já que é sobre # de iterações essencialmente.

Existem abordagens para algoritmos que lhe permitirá reduzir o número de iterações que você precisa. Um exemplo destes são " divisão & Conquer " algoritmos como Quicksort , que se bem me lembro é O (nlog (n)).

É difícil chegar a uma alternativa melhor para o seu exemplo sem saber mais especificamente o que você está tentando realizar.