Modulo 7 Complexidade

Módulo 7

Complexidade de Algoritmos
Algoritmos e Estruturas de Dados II
C++
Rone Ilídio

Tempo de execução de um programa
•

Qual algoritm executará mais rápido?

int main(){
Hour: 22 Min: 40 Second: 15 Milliseconds: 906
SYSTEMTIME inicio,fim;
Hour: 22 Min: 40 Second: 15 Milliseconds: 953
GetSystemTime(&inicio);
long aux = 1; for(long i=1; i<=10000000; i++) aux++; GetSystemTime(&fim); cout << "Hour: "<<inicio.wHour<<" Min: "<<inicio.wMinute<<" Second: "<< inicio.wSecond<<" Milliseconds: "<<inicio.wMilliseconds; cout << "\nHour: "<<fim.wHour<<" Min: "<<fim.wMinute<<" Second: "<< fim.wSecond<<" Milliseconds: "<<fim.wMilliseconds; getch(); }

Tempo de execução de um programa
• Qual algoritm executará mais rápido?
#include <conio.h>
#include <iostream.h>
Hour: 22 Min: 29 Second: 32 Milliseconds: 546
#include <Windows.h>
Hour: 22 Min: 30 Second: 12 Milliseconds: 453
#include <time.h> int main(){
SYSTEMTIME inicio,fim;
GetSystemTime(&inicio);
long aux = 1; for(long i=1; i<=100000; i++) for(long i=1; i<=100000; i++) aux++; GetSystemTime(&fim); cout << "Hour: "<<inicio.wHour<<" Min: "<<inicio.wMinute<<" Second: "<<inicio.wSecond
<<" Milliseconds: "<<inicio.wMilliseconds;

cout << "\nHour: "<<fim.wHour<<" Min: "<<fim.wMinute<<" Second: "<<fim.wSecond
<<" Milliseconds: "<<fim.wMilliseconds; getch(); }

Tempo de execução de um programa
• Estimar o tempo  considere cada operação um ciclo int main(){
2 ciclo long aux = 1, n; cout << "Digite um numero:"; cin >> n; for(long i=1; i<=n; i++)
N*
aux++;
1 ciclo cout << "aux:"<<aux;
1 ciclo getch(); }

2+N*1 + 1=3+N

Tempo de execução de um programa
• Estimar o tempo int main(){ long aux = 0, n; cout << "Digite um numero:"; cin >> n; for(long a=1; a<=n; a++) for(long b=1; b<=n; b++) aux++; cout << "aux:"<<aux; getch(); }

2 ciclos

N*
N*
1 ciclo
1 ciclo
2+n*n*(1)+1=3 + n2

Tempo de execução de um programa
• O tempo de execução é dado em relação a uma função, denominada função de complexidade f(n), onde n é o número de entradas