所有的算法可以大概分为以下三种类型：
1．贪婪算法(greedy algorithm)
该算法每一步所做的都是当前最紧急、最有利或者最满意的，不会考虑所做的后果，直到完成任务。这种算法的稳定性很差，很容易带来严重后果，但是，如果方向正确，那该算法也是高效的。
2．分治算法(divide-and-conquer algorithm)
该算法就是将一个大问题分解成许多小问题，然后单独处理这些小问题，最终将结果结合起来形成对整个问题的解决方案。当子问题和总问题类型类似时，该算法很有效，递归就属于该算法。
3．回溯算法(backtracking algorithm)
也可以称之排除算法，一种组织好的试错法。某一点，如果有多个选择，则任意选择一个，如果不能解决问题则退回选择另一个，直到找到正确的选择。这种算法的效率很低，除非运气好。比如迷宫就可以使用这种算法来实现。
实际上，我们对算法的效率高低评价，主要是在时间和内存之间权衡。根据实际情况来决定，比如有的客户不在乎耗用的内存是多少，他在乎的是执行的速度，那么一个用内存来换取更高执行时间的算法可能是更好的。同样，有的客户可能不想耗用过多内存同时对速度也不是特别要求。不管怎样，效率是算法的主要特性，因此关注算法的性能尤其重要！标准的测量方法就是找出一个函数(增长率)，将执行时间表示为输入大小的函数。选择处理的输入大小来说增长率比较低的算法！
计算增长率的方式：
1．测量执行时间
通过System.currentTimeMillis()方法来测试
部分代码:
// 测量执行时间
static void calculate_time(){
long test_data = 1000000;
long start_time = 0;
long end_time = 0;
int testVar = 0;
for (int i = 1; i <= 5; i++){
// 算法执行前的当前时间
start_time = System.currentTimeMillis();
for(int j = 1; j <= test_data; j++){
testVar++;
testVar--;
}
// 算法执行后的当前时间
end_time = System.currentTimeMillis();
// 打印总共执行时间
System.out.println("test_data = " + test_data + "\n" +
"Time in msec = " + (end_time - start_time) + "ms");
//环后将循环次数加倍
test_data = test_data * 2;
}
}
以上代码将分别计算出1000000、2000000、4000000...次的循环时间。
缺点：
Ø 不同的平台执行的时间不同
Ø 有些算法随着输入数据的加大，测试时间会变得不切实际！
2．指令计数
指令---指编写算法的代码.对一个算法的实现代码计算执行指令次数。两种类型指令：不管输入大小，执行次数永远不变；执行次数随着输入大小改变而改变。一般，我们主要测试后一种指令。
例：计算指令执行次数
static void calculate_instruction(){
long test_data = 1000;
int work = 0;
for (int i = 1; i <= 5; i++){
int count = 0;
for (int k = 1; k <= test_data; k++){
for(int j = 1; j <= test_data; j++) {
// 指令执行次数计数
count++;
work++;
work--;
}
}
System.out.println("test_data = " + test_data + "\n" +
"Instr. count = " + count );
test_data = test_data * 2;
}
}
3．代数计算
代码1：
long end_time = 0; t1
int testVar = 0; t2
for (int i = 1; i <= test_data; i++){ t3
testVar++; t4
testVar--; t4
}
假设t1 --- t4分别代表每条语句的执行时间，那么，以上代码的总执行时间为：t1 + t2 + n(t3 + 2t4).其中n = test_data,当test_data增大时，t1和t2可以忽略不计，也就是说，对于很大的n,执行时间可以近似于：n(t3 + 2t4)
4．测量内存使用率
一个算法中包含的对象和引用的数目，越多则内存使用越高，反之越低。
比较增长率：
1.代数比较法
条件1：c≦ f(n)/g(n) ≦ d (其中c和d为正常数，n代表输入大小)
当满足以上条件1时，则f(n)和g(n)具备相同的增长率，或者两函数复杂度的阶相同！
如：f(n) = n + 100 和 g(n) = 0.1n + 10两函数就具备相同的增长率。
条件2： 当n增大时，f(n)/g(n)趋向于0
当满足此条件2时，则该两个增长函数有不同的增长率。
比如：f(n) = 10000n + 20000 和 g(n) = n?2 + n + 1 。请大家比较以上两函数增长率是否一样，如果不一样，谁的增长率小？
2．大O表示法
如果f的增长率小于或者等于g的增长率，则我们可以用如下的大O表示法：
f = O(g)
O表示on the order of
将代码1的代数增长率函数用大O表达式如下：
f(n) = t1 + t2 + n(t3 + 2t4)
= a1*n + a
= O(n)
其中a1 = t3 + 2t4; a = t1 + t2
3．最佳、最差、平均性能
对每一个算法不能只考虑单一的增长率，而应该给出最佳、最差、平均的增长率函数
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
