文章目录
一、复杂度
1、判断算法优劣的方法
1.1 事后统计法
通过
统计、监控、利用计算机机器【处理器等】对不同算法的运行时间进行比较，从而确定算法效率的高低，但有局限性。
1.2 事前分析估算
在计算机程序编制前，依据
统计方法对算法进行估算。
2、时间复杂度
- 通常用
O来表示；- 算法的执行效率；
- 算法的执行时间与算法的输入值之间的关系。
2.1 O(1)
#include<stdio.h>
void O1(int num)
{
int x = num;
printf("%d\n", x);
}
int main()
{
O1(2);
return 0;
}
2.2 O(logN)
void OlogN(int num)
{
int i=1;
while(i<num)
{
i = i*2;
printf("%d\n", i);
}
}
int main()
{
OlogN(8);
return 0;
}
2.3 O(N)
void ON(int num)
{
int i=0;
for(i=0; i<num; i++)
{
printf("%d\n", i);
}
}
int main()
{
ON(8);
return 0;
}
2.4 O(MN)
void OMN(int num)
{
int i, total;
for(i=0; i<num1; i++)
{
total += i;
}
for(i=num1; i>0; i--)
{
total -= i;
}
printf("%d\n", total);
}
int main()
{
OMN(8);
return 0;
}
2.5 O(NlogN)
void ONlogN(int num)
{
int i, j, total;
for(i=0; i<num; i++)
{
while(j<num)
{
total +=j;
j = j*2;
}
}
}
int main()
{
ONlogN(8);
return 0;
}
2.6 O(N2)
void ON2(int num)
{
int i, j;
for(i=0; i<num; i++)
{
for(j=0; j<num; j++)
{
printf("-");
}
}
}
int main()
{
ON2(8);
return 0;
}