Em ciência da computação, a complexidade de algoritmos se refere ao quanto de tempo e memória um algoritmo consome para executar uma tarefa de acordo com o tamanho da sua entrada. Em geral, são avaliados o consumo de tempo e memória, porém neste post falarei somente da complexidade de tempo.
Existem duas grandes formas de quantificar a eficiência de um algorítimo, o método empírico e o método analítico. Essas formas podem variar de acordo com o aspecto de eficiência que deseja medir.
De modo que o tempo de execução de um algoritmo pode ser dado como uma função T(n) do tamanho n da sua entrada. Por exemplo, um programa pode ter tempo de execução T(n) = n2 + n + 1. A unidade de T(n) é em principio instrução executada.
A medida do custo de execução de um algoritmo depende principalmente do tamanho da entrada dos dados. É comum considerar o tempo de execução de um programa como uma função do tamanho da entrada. Para alguns algoritmos, o custo de execução é uma função da entrada particular dos dados, não apenas do tamanho da entrada.
Algoritmo Quicksort
Função clock() e a macro CLOCKS_PER_SEC Para encontrar o tempo de execução de um programa precisamos usar ela duas vezes, uma para capturar o tempo inicial e outra para capturar o tempo final da execução. Se fizermos o tempo final - tempo inicial teremos o tempo de execução do programa em milissegundos.