C Complexidade de Algoritmo ( Estrutura de Dados)

[Joice Fernanda ferreira]

Boa Tarde

Amigos,

Preciso muito da ajuda de vocês para realizar este exercicio eu não possuo muito entendimento e meus colegas da turma tambem estão com dificuldade. 

 

1.    Calcule a complexidade, no pior caso, do fragmento de codigo abaixo

int i, j ,k,s;

  for (i=0; i < N - 1; i++)

     for( j = i+1; j < N; j ++ )

       for ( k = 1; k < j ; k ++ )

          s = 1 ;

 

[Leonardo0308]

Boa tarde @Joice Fernanda ferreira

 

Qual o exercício e qual a dificuldade?   

[Detetive Virtual de SSDs]

@Joice Fernanda ferreira Olá, Joice, boa tarde e seja bem vinda ao Fórum do Clube do Hardware

 

Primeiramente, qual o objetivo de tal exercício?

[Joice Fernanda ferreira]

@Leonardo0308 Eu vou ser bem sincera eu não sei fazer este exercicio .

O meu professor me passou uma lista de Estrutura de dados onde contem Quick Sort, Bubble Sort, Heap, entre outras ordenações e arvore.

Até ai é sucesso porém este tema de complexidade de algoritmo esta bem difícil para mim, e a materia é online.

adicionado 0 minutos depois

@GabrielLP14

Eu vou ser bem sincera eu não sei fazer este exercicio .

O meu professor me passou uma lista de Estrutura de dados onde contem Quick Sort, Bubble Sort, Heap, entre outras ordenações e arvore.

Até ai é sucesso porém este tema de complexidade de algoritmo esta bem difícil para mim, e a materia é online.

[Leonardo0308]

Como o colega @GabrielLP14 disse...qual o objetivo do exercício?

[Joice Fernanda ferreira]

@Leonardo0308 esta descrito dessa maneira, calcule a complexidade, no pior caso, do fragmento de codigo abaixo.

Exercicos 19 á 23 foram os que me surgiram duvidas

 

Segue o anexo 

1-lista.docx

[Leonardo0308]

Não tenho como baixar arquivos...

 

Poderia colocar a questão direto aqui no fórum?

[Joice Fernanda ferreira]

@Leonardo0308 Realizei a edição da questão no forum.

[Leonardo0308]

Normalmente para você começar essa questão, você verifica a complexidade contando o numero de loop dentro de loop, no seu caso tem 3 loops um dentro do outro, então a complexidade é O³.

 

Mas como não foi dado tempo e nem operações ou outra coisa na questão, normalmente se acaba ai.

 

Caso passe o tempo ou operações ou peça mais coisas é só aplicar a formula que eu não lembro de cabeça  

[Joice Fernanda ferreira]

@Leonardo0308 então não existe nenhuma conta para fazer rs ? apenas olhar esta formula O ao cubo !

[Flávio Pedroza]

1 hora atrás, Joice Fernanda ferreira disse:

@Leonardo0308 então não existe nenhuma conta para fazer rs ? apenas olhar esta formula O ao cubo !

Pode ser que seu professor cobre os cálculos.

Por exemplo, questão 21, a complexidade seria N*2*N = 2*N^2, logo O(N^2) (os números constantes são descartados e prevalece o N de maior ordem)

Edit: Veja esse pdf, onde tem um exemplo  prático do calculo:

http://web.cs.iastate.edu/~smkautz/cs228s11/examples/algorithms/notes_on_big_O_from_recitation.pdf

Mas, como o autor mesmo disse, basta multiplicar a quantidade de vezes que o loops são executados para ter a resposta, mas como disse em cima, pode ser que não seja só isso que seu professor queira.

[Leonardo0308]

12 horas atrás, Joice Fernanda ferreira disse:

então não existe nenhuma conta para fazer rs ? apenas olhar esta formula O ao cubo !

 

Existir existe, complementando o que o colega @Flávio Pedroza disse, ele pode pedir o numero de operações que podem ser executadas em N segundos ou o contrario em N segundos quantas operações podem ser executadas.

 

Mas pela questão que você escreveu é só colocar o " O³ " mesmo. É importante você conseguir definir se o algorítimo vai ser uma constante ou " O¹ " ou " O² " ou " O³ ", pois assim não terá dificuldade em bater o olho e definir o calculo a ser feito ou até mesmo analisar um gráfico de complexidade.