Worst Case Tempo Complexidade para um algoritmo

Question

O que é o pior caso Tempo Complexidade t (n): - Estou lendo este livro sobre algoritmos e como exemplo como obter o T (n) para .... como a seleção Classificar Algoritmo

---

Como se eu estou lidando com o 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

deixe-me escrever um pseudocódigo

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]

-------- vou escrevê-lo em C # também ---------------

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;
  }
}

==================

Agora como obter o t (n) ou como seu conhecido a complexidade pior momento caso

Answer 1

sara jons O conjunto de slides que você já referenciados - e o algoritmo nele

A complexidade está a ser medido para cada operação primitiva / atómica no loop for

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

As lâminas taxa este ciclo como 2n + 2, pelas seguintes razões:

O conjunto inicial de j = 0 (1 op)

A comparação de j

O incremento de j ++ (n ops)

A condição final para verificar se j

Em segundo lugar, a comparação dentro do loop

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

Esta é avaliado como n ops. Assim, o resultado se você somar +1 op, n ops, on ops, um op, on ops = 3n + 2 complexidade. Assim T (n) = 3n + 2

Reconhecer que T (n) não é o mesmo que o (n).

Answer 2

Isso seria O (n ^ 2).

A razão é que você tem um único loop aninhado em outro loop for. O tempo de execução para o interior para o laço, S (n), acontece para cada iteração do exterior para o circuito, que por sua vez é O (n). A razão pela qual cada um destes são individualmente O (n) é porque eles tomam uma quantidade linear do tempo, dado o tamanho da entrada. Quanto maior for a entrada de mais tempo demora em uma escala linear, n.

Para trabalhar a matemática, que neste caso é trivial, apenas múltiplos a complexidade do circuito interno pela complexidade do laço externo. n * n = n ^ 2. Porque lembre-se, para cada n no loop externo, você deve novamente fazer n para o interior. Para esclarecer: n vezes para cada n.

O (n * n).

O (n ^ 2)

Answer 3

A propósito, você não deve misturar complexidade (denotado por big-O) e a função T. A função T é o número de passos que o algoritmo tem que passar para uma determinada entrada.

Assim, o valor de T (n) é o número real de passos, enquanto que O (algo) indica uma complexidade. Pelo abuso convencional de notação, T (n) = O (f (n)) significa que a função de T (n) é de, no máximo, a mesma complexidade que outra função f (n), que geralmente será o mais simples função possível da sua classe complexidade.

Isso é útil porque nos permite concentrar-se na grande figura: Agora podemos facilmente comparar dois algoritmos que podem ter muito diferente de aparência funções T (n) olhando como eles executam "a longo prazo" <. / p>

Answer 4

outro flashback de doutorado-comp aqui.

Em primeiro lugar, a função T é simplesmente a quantidade de tempo (geralmente em algum número de etapas , sobre o qual mais abaixo) um algoritmo leva para realizar uma tarefa. O que um "passo" é, é um pouco definido pelo uso; por exemplo, é convencional para contar o número de comparações em algoritmos de ordenação, mas o número de elementos procurou em algoritmos de busca.

Quando falamos sobre o tempo do pior caso de um algoritmo, que geralmente expressam isso com "notação big-O". Assim, por exemplo, você ouve esse tipo bolha leva O (n²) tempo. Quando usamos a notação O grande, o que estamos realmente dizendo é que o crescimento de alguma função - neste caso T - não é mais rápido do que o crescimento de alguma outra função vezes por constantes. Isso é

T (n) = O (N²)

meios para qualquer n , não importa quão grande, há uma constante k para que T (n) = kn² . A ponto de alguns confustion aqui é que nós estamos usando o sinal "=" de forma sobrecarregada: isso não significa que os dois são igual no sentido numérico, só que nós estamos dizendo que < em> T (n) é delimitada por kn² .

No exemplo na sua pergunta prolongada, parece que eles estão contando o número de comparações no loop for e no teste; ele iria ajudar a ser capaz de ver o contexto e a pergunta que está respondendo. Em qualquer caso, porém, ele mostra por que nós como big-O notação: W (n) aqui é O (n) . (Prova: existe uma constante k, nomeadamente 5, para os quais W (n) = K (3n) 2 Segue-se pela definição de O (n) . .)

Se você quiser saber mais sobre isso, consulte qualquer texto bons algoritmos, por exemplo, Introdução aos Algoritmos , por Cormen et al.

Answer 5

códigos de escrita pseudo de pesquisa, inserção e informações dos alunos remove da tabela hash. calcular os melhores e os piores complexidades de tempo caso

Answer 6

3n + 2 é a resposta correta, tanto quanto o circuito está em causa. Em cada etapa do ciclo, 3 operações atómicas são feitas. j ++ é, na verdade, duas operações, não apenas um. e j