No geral, as respostas até o momento tratam a mensuração da eficiência em termos práticos.
Vou dar uma resposta em termos teóricos, já que você faz duas perguntas: Como determinar as equações de complexidade e se há outro método.
Para responder a primeira pergunta, em primeiro lugar recomendo um livro introdutório de algoritmos que ensine notação Big-O.
Os livros que recomendo são:
- Algoritmos: Teoria e Prática - Conhecido internacionalmente, particularmente só tive acesso à versão em inglês.
- Algorithms Unlocked - Não tive acesso, mas é bem recomendado por ser uma versão menos longa do livro anterior. Escrito pelo mesmo autor renomado.
- Schaum's Outline of Discrete Mathematics - Gosto deste livro por ser bem direto, mais apropriado pra quem não é iniciante talvez. Não exatamente focado em algoritmos, abrange várias áreas importantes das ciências da computação (particularmente sinto ser até mais acessível que "Algoritmos: Teoria e Prática" em certos pontos no tocante a algoritmos).
Vou reduzir a análise em miúdos, de forma não rigorosa, sem envolver loop invariants, etc.
Primeiro o mais fácil de analisar, o caso 2.
Este caso consiste em apenas um loop que repete uma operação de complexidade O(1). A quantidade de repetições é diretamente proporcional ao valor de entrada da função. Se o argumento x
for N
, então o loop será repetido N
vezes. Fora o loop, o corpo da função só tem outras operações de complexidade O(1):
int Y(int x) { // O(1)
int soma=0; // O(1)
// O(1) O(1) O(1)
for( int i=0; i<=x; ++i )
soma+=i; // O(1)
// O() do loop = O(x) == O(1) + x*O(1) + x*O(1) + x*O(1)
return soma; // O(1)
}
// O() da função = O(x) == O(1) + O(1) + O(x) + O(1)
Portanto esta função tem complexidade O(N) no tempo. Nota-se que esta função realiza seu cálculo com uma quantidade fixa de variáveis locais somente, portanto ela é O(1) no espaço usado (ou seja, não precisa de mais memória dependendo da entrada).
O primeiro caso é uma função recursiva, e a análise de complexidade se torna recursiva também. Existe uma teoria sólida para isto, mas irei me ater a uma
explicação simplória.
Note que, todas as operações no corpo da função, exceto a própria chamada recursiva, são O(1). As chamadas recursivas ocorrerão até que se chegue a condição de término. Nota-se que para uma entrada x = N
, ocorreram N
chamadas. Dado que em cada chamada, fora a chamada recursiva, são realizadas operações O(1), então a complexidade no tempo desta função também é O(N).
A complexidade no espaço desta função difere do caso 2. Pelo fato de ser uma função recursiva cujo resultado precisa ser agregado como uma soma no final, ela não é uma função tail-recursive, e portanto não é possível que o compilador otimize sua função utilizando esta técnica.
Dado que tail-recursion não é possível, a cada chamada recursiva é preciso que se empilhe na pilha de chamada um número fixo de dados (argumentos da função, endereço de retorno, etc). Ou seja, para N
chamadas, ocorreram N
empilhamentos de dados de um tamanho determinado, portanto a função é O(N) no espaço que utiliza também.
Respondendo à segunda pergunta: Há outro método?
Você tem duas soluções para o problema, uma é O(N) no tempo e O(N) no espaço, uma é O(N) no tempo e O(1) no espaço.
Uma alternativa seria procurar uma solução cuja complexidade não dependa do valor de entrada, será que é possível uma solução O(1) no tempo e O(1) no espaço?
Note que:
- y = 1 + 2 + 3 ... + (x - 2) + (x - 1) + x
- y - x * x = (1 - x) + (2 - x) + (3 - x) ... + [(x - 2) - x] + [(x - 1) - x] + (x - x)
- -(y - x * x) = (x - 1) + (x - 2) + (x - 3) ... + 2 + 1 + 0
- x * x - y = 1 + 2... + (x - 3) + (x - 2) + (x - 1)
- x * x - y = y - x
- x * x + x = 2y
- y = x * (x + 1) / 2
Desta formula (uma dedução básica da soma dos elementos de uma progressão aritmética), é possível obter o valor da soma a partir do valor de entrada com complexidade O(1), ou seja, sem loops.
Então o método mais eficiente seria:
int Z(int x) { // O(1)
return (x * (x + 1)) / 2; // O(1)
}
(Se você já se perguntou na vida onde que iria usar PA e PG ensinado na escola, tá aí ;-) )
Se você quisesse ser mais eficiente ainda, com C++11 poderia declarar a função como
constexpr
.
constexpr int Z(int x) {
return (x * (x + 1)) / 2;
}
Assim, a maioria dos compiladores que suporta C++11 faria o cálculo da soma em tempo de compilação, incorrendo em nenhum cálculo em tempo de execução, quando o argumento passado for uma constante. Caso o argumento não seja uma constante (i.e. um valor de tempo de execução), a função obtém a mesma eficiência de uma versão inline
.