C Analise da complexidade de algoritmo

[UmPrograma]

Boa tarde.

 

Estava aqui pensando sobre a importancia da eficiencia do codigo no programa e tal.

 

Ai analisando um programa de soma de vetores, percebi que sempre, valor assintotico, é O(n).

 

Sempre em funcao do numero de entradas. Sendo essa o numero de operacoes, e as demais classes assintoticas ficariam desconsideras. Como somar e multiplicar constante, O(1).

 

Minha dúvida é se nesse programa, que é ainda do vetor. (O que peguei para analisar)

 

Soma de vetores

para I de 1 até N faça S ← X + Y Fim para

Número de passos = número de somas (N)

 

Me parece que nao existe pior, medio e melhor caso nesse programa, sendo tudo em funcao do numero de entradas. É isso mesmo? 

 

[UmPrograma]

Quando declaramos variáveis existe um custo para o programa?

 

Seria um custo constante? Complexidade constante, O(1)?

[Plástico Bolha]

Citação

Quando declaramos variáveis existe um custo para o programa?

Sim, de fato existe um custo computacional para realizar esta operação, no entanto ...

 

Em 12/12/2018 às 07:27, UmPrograma disse:

Quando declaramos variáveis existe um custo para o programa?

 

Seria um custo constante? Complexidade constante, O(1)?

   Geralmente na análise de complexidade de algoritmos é pego somente o termo de maior relevância dentro do algoritmo, e é desprezado os termos de menor relevância, se pro seu algoritmo contabilizar tal declaração se torna algo essêncial para montar a equação e fazer a análise assintótica, então sim, deve-se contabilizar, caso este termo (declaração) seja desprezível dado o resto do algoritmo, então não há porque contabilizá lo, isso depende muito do objetivo da sua análise, por exemplo:

// Imagine que está função faz a soma dos elementos de uma matriz quadrada
function sumMatrix(matrix: number[][]) {
    // Faz sentido contabilizar o custo da declaração de sum ?
    var sum = 0;
    for (var i = 0; i < matrix.length; i++) { // N - 1
        for (var j = 0; j < matrix.length; j++) { // (N - 1)*(N - 1)
            sum += matrix[i][j]; // (N - 1)*(N - 1)
        }
    }
	// Faz sentido contabilizar o custo deste retorno ?
    return sum;
}
// Faz sentido contabilizar o custo desta declara + retorno ?
var totalSum = sumMatrix(matrix)
console.log(totalSum) //Faz sentido contabilizar o custo desta impressao deste numero no console ?

   Você teria algo desse tipo no final, por exemplo

Citação

(N - 1) + ((N - 1)*(N - 1)) + ((N - 1)*(N - 1))

(Não sei fiz a análise deste algoritmo 100% correta, no entanto, nem é essa a ideia deste post)

   Desta forma esta equação deveria ser simplificada para que fosse possível fazer a análise assintótica do seu algoritmo, de qualquer forma, fica claro que seria uma equação de ordem 2, obivamente porque se trata de uma matriz quadrada. Então teriamos algo como no pior caso O(n²).

 

   Perceba algo interessante sobre a sua análise! Iria fazer alguma diferença se adicionar aquelas declarações ali em cima? Como por exemplo:

Citação

var sum = 0

var totalSum = sumMatrix(matrix)

console.log.log(totalSum)

   Nâo ! Isto não mudaria a ordem 2 da equação, e a complexidade do seu Big O não deixaria de ser O(n²), portante, para este algoritmo em questão tais declarações se tornam despreziveis. 

 

   Na análise assintótica de um algoritmo, cada caso é um caso, e deve-se ter total compreensão do que o seu algoritmo faz, e qual o objetivo dá análise ou qual é exatamente a métrica que se está buscando na análise.

 

Por exemplo, se este algoritmo fosse analisado:

function sumNumbers(x,y) {
    var result = x + y // Vale a pena contabilizar esta atribuição + operação matemática ? Sim !
    return result // vale a pena contabilizar este retorno ? Sim !
}

   Neste caso valeria a pena contabilizar a declaração e o retorno das 2 linhas, pois a equação simplificada deste algoritmo não iria ser de ordem maior que 2 . . . Acredito que o melhor a se fazer para analisar o algoritmo seria antes de analisar o algoritmo de forma mecânica/matemática, seria compreender o contexto do algoritmo.

 

[UmPrograma]

@Plástico Bolha  Olá, bom dia!

Outra duvida minha é em relação ao printf e ao scanf....

 

Eles tem algum custo. Acho que sim né

 

O  scanf atribui um valor a variavel.

 

Na imagem anexada, apresento um algoritmo de soma de vetores. Nele sei que o custo do for é 2(n+1) . (vi em um video)

Ai tenho dois for, logo ao final seria 4n + 2 , mais ainda os valores que que sao constantes (aqueles que so tem custo 1)

 

Mas, diante do seu exposto me parece ser desnecessario realmente falar das constantes. Mas ainda em relação a soma de vetores, olhe se estou enganado.

 

Daria ao total 4n + 9. Desconsiderei os printf, pois não sei do seu custo ao certo.