C Sobre complexidade do meu algoritmo

[ucas_santoss]

 

 

 

 

 

 

 

alguém poderia me ajudar a localizar o ponto especifico e qual seria a complecidade do mesmo?

 

 

 

 

 

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int char_em_int(int n);    //Função no qual transforma o arquivo char em uma matriz de numeros inteiros
int excentricidade(int *e,int cont,int z, int x);//Função no qual pega a excentricidade dos vertices e guarda no vetor 
int matriz[100][100]; //Matriz de Adjacencia do Grafo
int i, j, i1, j1; //indices auxiliares para varrer a matriz
FILE *arquivo;//Localizar o arquivo texto 
bool verificacao (int *v,int j1,int x);//Função de verificação, a mesma verifica se o vertice ja foi visitado/inserido no vetor
bool arquivloc; //Verifica se o arquivo foi encontrado ou nao
bool Sair;//escolher sair do programa ou solicitar novo arquivo
char qualarquivo[30];//Digite o nome do arquivo que vai utilizar
//*-=-=-=-=-=-=--=-* VARIAVEIS DECLARADAS *-=-=-=-=-=-=--=-*//
int x,z; //Auxiliares apenas para varrer os vetores
int *vlonge;    //Vetor para verificação de qual vertice mais longe
int *vexcentri;    //Vetor para verificação da excentricidade
int quant;  //A quantidade de Vertices do grafo
char correrm;    //Variavel usar para pecorre toda a matriz do arquivo texto
char auxconv[1]; //Variavel auxiliar que vai está recebendo apenas um caractere do arquivo para a conversão para int
int contador = 1; //Dependendo da função que está variavel auxiliar esteja, ela irá contar a excentricidade e o numero de vertices

//*-=-=-=-=-=-=--=-* INICIO DO SOFTWARE *-=-=-=-=-=-=--=-*//

main(){
Sair = false;
do{    //verifica se o user gostaria de inserir outro arquivo ou sair do sistema
    arquivloc = false;
    do{//Verificando se o arquivo digitado e valido
        system("cls");
        printf("\n<----------------------> EXCENTRICIDADE <----------------------> \n Informe o nome do arquivo desejado ou S para finalizar: ");
        scanf ("%s",qualarquivo);
        
        if (!strcmp (qualarquivo,"S") || !strcmp(qualarquivo,"s"))
        {
            goto fim;
        }
        
        strcat (qualarquivo,".txt");
        
        if((arquivo = fopen(qualarquivo,"r")) != NULL)
        {
            arquivloc = true;
            printf("\nPesquisando arquivo..\n");
            printf("Arquivo localizado com sucesso!\n");
            system ("pause");
        }else{
            printf("\nPesquisando arquivo..\n");
            printf ("Arquivo inexistente, tente novamente!\n");
            system ("pause");
        }
        
    }while(arquivloc != true);//Fim da Verificação se o arquivo foi valido ou não
    
        for (i=0; i<100; i++){//Zerando a Matriz
            for (j=0; j<100; j++){
                matriz[i][j] =0;
            }
        }
        
        system("cls");
         printf("\nMatriz de adjacencia do arquivo:\n\n");
         
          quant = char_em_int(quant);
          vlonge = (int*)calloc(quant, sizeof(int));//alocação dinamica do tamanho do vetor v
          vexcentri = (int*)calloc(quant, sizeof(int));//alocação dinamica do tamanho do vetor e
        for(i=0; i<quant ; i++) { //Realizando a impressão da Matriz de Adjacencia
            for(j=0; j<quant; j++){
                printf("%d ",matriz[i][j]);
            }
        printf("\n");// pulando linha
        }
    printf("\n");    
    
//*-=-=-=-=-=-=--=-* CODIGOS DEVEM SER IMPLEMENTADOS A PARTIR DESTA LINHA *-=-=-=-=-=-=--=-*//

for(i=0; i<quant; i++){    //Iniciando o for para verificar a excentricidade e o vertice mais distante
    x=0; 
    z=0; 
    contador = 1;
    vlonge[x] = i;
        for(j = 0; j < quant; j++){
            if(i != j && matriz[i][j] == 1){    //Esta inserindo os vertices que tem caminho direto no vetor (v[x]) 
                x++;    //  vertice no qual esta sendo comparado.
                vlonge[x] = j;
                vexcentri[x] = contador;//já que temos um caminho direto, esta inserindo a "excentricidade" que é 1
            }
       }
       contador++;//Cont da "Excentricidade" recebe 2, ja que se entra no proximo loop
               while(x < quant-1){                                                                
                   z++;                                                                    
                   i1 = vlonge[z];//Vai ser testado outro vertice,  o proximo da posição do vertor (v[]x)
                       for(j1=0; j1<quant; j1++){
                           if(i1 != j1 && matriz[i1][j1] == 1 && verificacao(vlonge,j1,x) != true){ //Esta inserindo no verto (v[x]) os vertices que tem caminho direto com
                               x++; //o vertice no qual esta sendo comparado e não foi inserido ainda.
                               vlonge[x] = j1;
                               contador = excentricidade(vexcentri,contador,z,x);
                        }
                    }
            } //rodando o loop ate o vetor v[x] não for totalmente preenchido
    printf("Excentricidade do Vertice %d: %d\n",i+1,vexcentri[quant-1]);    //Realizando a Impressão da Excentricidade dos Vertices
} //Fim do FOR dda excentricidade e do vertice mais distante  
    printf("\n\nDesenvolvido por: Erickson ian, Joao Lucas, Leiliane dantas, Adrielison\n");

//*-=-=-=-=-=-=--=-*FIM DO CODIGO *-=-=-=-=-=-=--=-*//

fclose(arquivo);//Para fechar o arquivo
free(vlonge); //Realizando a Liberação de memoria do vetor v
free(vexcentri); //Realizando a Liberação de memoria do vetor e
printf("\n\n");
system ("pause");
    
}while(Sair != true); //Fim da verificação se o usuario quer inserir outro arquivo ou se deseja sair

fim:
return 0;
}
int char_em_int(int n){
    j1= 0;
    i1= 0;
    contador = 1;
        while((correrm=fgetc(arquivo))!=EOF){ //Função para correr todo o arquivo adcionado.
    
            if(correrm == '1' || correrm == '0'){ //Comparando se o caractere é 1 ou 0
                auxconv[0] = correrm; // apenas uma variavel auxiliar que vai recebe 0 ou 1(apenas um deles)
                matriz[i1][j1] = atoi(auxconv); //convertendo de char para int e jogando na matriz
                j1++;
            }
            if(correrm == '\n'){ // \n caso o arquivo vernha a ter alguma quebra de linha
                i1++; // percorrendo outra linha
                j1 = 0;    // j1 niciando na posição em 0
                contador++;    //Contador das linhas recebendo +1
            }
        }
    return contador; //Retornando a quantidade total de linhas da Matriz
}
bool verificacao (int *vlonge,int j1,int x){
    int y;
        for(y=0; y<=x; y++){ //Realizando a verificação se o vertice j1 ja foi ou está inserido no vetor 
            if(vlonge[y] == j1){    //se estiver inserido ele irá retornar True(verdadeiro)
                return true;
            }
        }
    return false; //se não estiver ele irá retorna false(falso)
}
int excentricidade(int *vexcentri,int cont,int z, int x){
    if(vexcentri[z] < contador){ //Já aqui ele está Esta inserindo em um vetor e[x] a distancia entre todos os outros vertices 
        vexcentri[x] = contador; //Auxiliar para colocar na mesma prosição que ele se encontra no outro vetor v[x]
    }else{ //o ultimo indice do vetor e[] teoricamente é a excentricidade e o ultimo do v[] seria o vertice mais distante
        contador++;
        vexcentri[x] = contador;
    }
return contador;    
}

[devair1010]

@ucas_santoss   Quem disse que ele seja complexo  ?  ,   por ser usado ponteiro nele pode ser que sim .

[ucas_santoss]

@devair1010 entrei em contato com o coordenador do meu curso ele observou e informou que eu deveria localizar o ponto critico do código e localizar qual seria a complexidade do mesmo, porém o desafio seria seria criar este código que verificar a excentricidade de um grafo, porém essa parte da complexidade me deixou digamos que "encucado"

[arfneto]

3 horas atrás, ucas_santoss disse:

@devair1010 entrei em contato com o coordenador do meu curso ele observou e informou que eu deveria localizar o ponto critico do código e localizar qual seria a complexidade do mesmo, porém o desafio seria seria criar este código que verificar a excentricidade de um grafo, porém essa parte da complexidade me deixou digamos que "encucado"

 

De https://pt.wikipedia.org/wiki/Complexidade_de_Tempo considere isso

 

Citação

Em ciência da computação, a complexidade de tempo de um algoritmo quantifica o montante de tempo tomado por este dado algoritmo rodar como uma função do comprimento de uma cadeia representando os dados de entrada[1]:226. A complexidade de tempo de um algoritmo é comumente expressada usando a notação big O, que exclui coeficientes e termos de baixa ordem. Quando expressado desta forma, a complexidade de tempo é dita ser descrita assintoticamente. Por exemplo, se o tempo requerido por um algoritmo em todas as entradas de tamanho n é no máximo 5n3 + 3n operações elementares para qualquer n (maior do que algum n0), a complexidade de tempo assintótica é O(n3).

 

provavelmente seu instrutor se refere a identificar a ordem de complexidade do algoritmo, e não o sentido usual de "complexo"....