Complexidade desse algoritmo!!

[mateusvilela]

E ai gente...

to precisanu prova a complexidade desse algoritmmo::

function exp (var x: integer; var n: integer): integer;

begin

| if (n = o)

| then exp := 1

| else

| begin

| | exp := x*exp(x,n-1);

| end;

end;

eu sei q a complexidade é O(n)

eu tenho q provar.......

alguem sabe????

[fariajp]

A complexidade é O(n) porque o loop será executado "n" vezes, sendo esse n o parâmetro da função

Para provar, faça um "chinês". Se entrar com n = 10, ele vai chamar a recursão para 9, dai para 8, 7, 6, 5, 4, 3, 2 e 1...

JP

[andrebf]

Eu acredito que seja, NA MINHA OPINIÃO, EUU ACHO,

Que a complexidade é n log(n) ou só log(n).

[EduardoS]

É O(n) mesmo, o trecho sera executado n vezes e não log(n) ou n*log(n), como exemplos:

for(int i = 0; i < n; i++)
   AlgumaTarefaInvariavel();

Nesse caso o AlgumaTarefaInvariavel sera executado n vezes, logo a complexidade é O(n).

O(log n)

for(int i = 1; i < n; i *= 2)
   AlgumaTarefaInvariavel();

Nesse caso AlgumaTarefaInvariavel sera executado log n vezes, ou seja, se n for 2 sera executado 1 vez, se n for maior que 2 e menor ou igual a 4, sera executado 2 vezes, se n for maior que 4 e menor ou igual a 8 n sera executado 3 vezes, etc.

for(int i = 0; i < n; i++)
   for(int j = 1; j < n; j *= 2)
      AlgumaTarefaInvariavel();

O prouto dos dois de cima, logo, O(n log n).

[andrebf]

Ok, errei.

A função dele não é recursiva? Eu achava que quando tínhamos uma função recursiva, a mesma teria complexidade log N ou N*logN. Eu achei que a complexidade O(N) existisse somente quando existisse um for sozinho (ou outra estrutura de repetição). No caso, não vi nenhum for, então só achei que seria nlogn.

[fariajp]

Não existe regra do tipo "um for é log(n)" ou "um while é n^2". A complexidade leva em consideração os loops, e quem manda é condição de término/incremento desses loops. Aí é onde está a pista de quantas vezes o loop vai rodar.

E assim é na recursão, que não deixa de ser um loop. Essa recursão é linear (é chamado sucessivamente com n-1). Se fosse chamado sucessivamente com n/2, seria log(n).

Well, complexidade é complexo

[EduardoS]

E no caso é uma recursão do tipo... (alguem lembra o nome?), que pode ser reescrita com um loop:

function exp (var x: integer; var n: integer): integer;
begin
  while (n != 0)
  begin 
    n = n - 1;
    exp := x*exp
  end;
end;

Ah, como ja faz anos que não faço nada em Pascal não tenho certeza se a sinataxe ta correta, mas a ideia é essa...