O Exercício Estrutura de Dados

Lista de Exercícios 2 (Noções de Complexidade)

Questões 1. Faça uma pesquisa e escreva um exemplo de algoritmo para cada uma das classes abaixo:

(a) O(1): ordem constante.

//busca de um valor no vetor pelo índice.

int buscaValor(int vetor[], int posicao){

        return vetor[posicao];

}

(b) O(logn): ordem logarítmica.

O vetor ordenado em que ocorre a busca é dividido por 2 em cada interação. No final o tamanho do vetor é igual a 2^interações. Aplicando log fica log n.

int buscaBinaria(int vetor[], int l, int r, int valor){

        int mid=(l+r)/2;

        while(l<=r){

                if(vetor[mid]==valor)return mid;

                if(vetor[mid]

                if(vetor[mid]>valor)r=mid-1;

}

return -1;

}

(c) O(n): ordem linear.

Considerando o pior caso, a complexidade vai depender de N que é o tamanho do vetor.

int busca valor(int vetor[],int tamanhoVetor,  int valor){

        for(int i=0;i

                if(vetor[i]==valor)return i+1;        

                else return -1;

        }

}

(d) O(n · logn): ordem log linear.

Para mim é a complexidade mais confusa. O exemplo que conheço é o mergeSort.

void mergeSort(int l, int r){

        if(l>=r)return;

        int mid=(r+l)/2;        

        mergeSort(l, mid);

        merSort(mid+1, r);

        int elementosL= mid-1+1;

        int elementosR=r-(mid+1)+1;

        int vetorL[elementosL];

        int vetorR[elementosR];

        for(int i=l;i<=mid;i++)

                vetorL[i-1]=v[i];//v é o meu vetor original

        for(int i=mid+1;i<=r;i++)

                vetorR[i-(mid+1)]=v[i];

        int posL=0, posR=0;

        for(int i=l;i<=r;i++){

                int elementoAtual;

                if(posL>=elementosL){

                        elementoAtual=vetorR[posR];

                        posR++;

                }

                else if(posR >=elementosR){

                        elementoAtual=vetorL[posL];

                        posL++;

                }

                else if(vetorL[posL] <=vetorR[posR]){

                        elementoAtual=vetorL[posL];

                        posL++;

                }        

                else {

                        elementoAtual=vetor[posR];

                        posR++;

                }

                v[i]=elementoAtual;

        }

}

(e) O(n 2 ): ordem quadrática.

Como eu tenho que percorrer dois vetores de tamanho N para trabalhar com uma matriz, a complexidade dela é n^2.

int descobrePosicaoValor(int matriz[][a], int valor, int *valorLinha, int *valorColuna){

for(int i=0;i

        for(int j=0;j

                if(matriz[i][j]==valor){

                        *valorLinha=i;

                        *valorColuna=j;

                }

}

(f) O(n 3 ): ordem cúbica.

Multiplicação de matriz é um exemplo famoso de n^3 pois tem que trabalhar com 3 vetores relacionados a linhas e colunas.

void multiplica (int linha1, int coluna1, int matriz1[][2],   int linha2, int coluna2, int matriz2[][2])

{

    int x, i, j;

    int resultado[linha1][coluna2];

    for (i = 0; i < linha1; i++)

    {

        for (j = 0; j < coluna2; j++)

        {

            resultado[i][j] = 0;