Jump to content

Dúvidas relativamente à complexidade de um algoritmo.


vasco16
 Share

Recommended Posts

Boas pessoal tenho as seguintes dúvidas:

Como escrevo uma expressão T(n) , que por exemplo me dá o numero de acesso a um vector?

e

Qual a ordem( o o-Grande (O (...)) do algoritmo?

O algoritmo pode ser algo simples como isto:

public static void s ( int [ ] table , int max) {
int [ ] count = new int [max + 1 ] ;
for ( int m = 0; m < table.length ; m++)
count [ table [m] ] + + ;
int i = 0;
for ( int j = 0; j < count.length ; j ++)
for ( int k = 0; k < count [ j ] ; k++)
table [ i ++] = j ;
}

Se existirem formulas , peço-vos que me indiquem.

Obrigado.

Link to comment
Share on other sites

1º -  isto devia estar na secção de algoritmia.

Geralmente para isso define-se o tempo de execução de cada linha de código (geralmente uma constante, c1, c2, c3, etc.), calcula-se o número de vezes que cada linha é executada, e no fim determina-se a complexidade do algoritmo.

Olhando para o teu caso:

1 public static void s ( int [ ] table , int max) {
2 int [ ] count = new int [max + 1 ] ;
3 for ( int m = 0; m < table.length ; m++)
4 count [ table [m] ] + + ;
5 int i = 0;
6 for ( int j = 0; j < count.length ; j ++)
7 for ( int k = 0; k < count [ j ] ; k++)
8 table [ i ++] = j ;
}

Se o tempo de execução de uma linha de código uma única vez for cX (X = nº da linha) e definirmos n = table.length(), então tens:

As linhas 1 e 2 são executadas uma vez, portanto têm tempo de execução c1+c2.

A linha 3 é executada n+1 vezes, tempo = c3 * (n+1).

A linha 4 é executada n vezes, tempo = c4 * n.

A linha 5 é executada uma vez, tempo = c5.

A linha 6 é executada max+1 vezes, tempo = c6*(max+1)

A linha 7 é executada n+max vezes, tempo = c7*(n+max)

A linha 8 é executada n vezes, tempo = c8*n

Sendo assim, o tempo de execução total, separando por factores, é  (c1+c2+c3+c5+c6+c7) + n * (c3+c4+c7+c8) + max * (c6+c7).

Como podes ver, o algoritmo é O(n+max).

Não respondo a dúvidas por mensagem.

Link to comment
Share on other sites

Então o tempo de execução é: (c1+c2+c3+c5+c6+c7) + n * (c3+c4+c7+c8) + max * (c6+c7) .

e o O é O de n , O(N)?

A complexidade O pode ser definida apenas em relação a uma variável como estás a fazer. A definição formal da complexidade O de um algoritmo é a de que,  para N suficientemente grande tem que existir uma constante K, tal que K*Complexidade(N) > tempo(N). tempo(N) é o tempo que demora a executar em função do N, no teu caso o tamanho do array

Assim, se um algoritmo for O(N), tem que existir uma constante K e um n0, tal que para qualquer n > n0, K*n > tempo(n).

Se fosse O(N^2), teria que existir um K e um n0, tal que para qualquer n > n0, K*n^2 > tempo(n).

Se queres considerar apenas a complexidade em n, neste caso tens que considerar max constante, e aí vês que o "maior" termo em n que aparece é uma constante x n, logo a complexidade é O(n).

Não respondo a dúvidas por mensagem.

Link to comment
Share on other sites

Então e se tiver um tempo assim:

T(n) = 27log + 4xn + 34

Como fica o O(n) ?

Se querias escrever T(n) = 27*log(n) + 4xn + 34 fica O(n) porque o termo em n "domina" o termo em log(n) (da mesma forma que um n^2 domina um n, para n suf. grande)

Não respondo a dúvidas por mensagem.

Link to comment
Share on other sites

Se querias escrever T(n) = 27*log(n) + 4xn + 34 fica O(n) porque o termo em n "domina" o termo em log(n) (da mesma forma que um n^2 domina um n, para n suf. grande)

Hum então alem de um O(1) dá-me um exemplo de outro O sem ser O(n).

E a respectiva função T(n).

Obrigado pela atenção.

Link to comment
Share on other sites

podes ter (pelo menos):

O(1)

O(log(n))

O(n)

O(n*Log(n))

O(n^2)

O(n^n)

Os dois últimos q assinalei são os q tu não queres nos teus programas se queres q funcionem bem e rapidamente.

Para funções T(n) é complicado pq há tantas diferentes para formar estas q nem consigo lembrar-me de cmo exemplificar

"[Os jovens da actual geração]não lêem porque não envolve um telecomando que dê para mirar e atirar, não falam porque a trapalhice é rainha e o calão é rei" autor: thoga31

Life is a genetically transmitted disease, induced by sex, with death rate of 100%.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.