算法的类型

所有的算法可以大约分为以下三种类型：

1．贪婪算法(greedy<wbr>algorithm) </wbr>

该算法每一步所做的都是当时最紧迫、最有利或许最满意的，不会思考所做的成果，直到完成任务。这种算法的稳定性很差，很简单带来严重成果，可是，若是方向正确，那该算法也是高效的。

2．分治算法(divide-and-conquer<wbr>algorithm) </wbr>

该算法就是将一个大问题分解成许多小问题，然后独自处置这些小问题，最终将成果结合起来形成对整个问题的解决方案。当子问题和总问题类型相似时，该算法很有用，递归就归于该算法。

3．回溯算法(backtracking<wbr>algorithm) </wbr>

也可以称之扫除算法，一种安排好的试错法。某一点，若是有多个挑选，则恣意挑选一个，若是不能解决问题则退回挑选另一个，直到找到正确的挑选。这种算法的功率很低，除非命运好。比方迷宫就可以运用这种算法来完成。

实际上，咱们对算法的功率凹凸评估，首要是在工夫和内存之间权衡。依据实际情况来决议，比方有的客户不在乎耗用的内存是多少，他在乎的是履行的速度，那么一个用内存来交换更高履行工夫的算法能够是更好的。相同，有的客户能够不想耗用过多内存一起对速度也不是独特需求。不论怎样，功率是算法的首要特性，因而重视算法的功能特别重要！规范的丈量方法就是找出一个函数(增加率)，将履行工夫表明为输入巨细的函数。挑选处置的输入巨细来说增加率比拟低的算法！

核算增加率的方法：

1．丈量履行工夫

经过System.currentTimeMillis()方法来测验

局部代码:

//<wbr>丈量履行工夫</wbr>

static<wbr>void<wbr>calculate_time(){</wbr></wbr>

long<wbr>test_data<wbr>=<wbr>1000000;</wbr></wbr></wbr>

long<wbr>start_time<wbr>=<wbr>0;</wbr></wbr></wbr>

long<wbr>end_time<wbr>=<wbr>0;</wbr></wbr></wbr>

int<wbr>testVar<wbr>=<wbr>0;</wbr></wbr></wbr>

for<wbr>(int<wbr>i<wbr>=<wbr>1;<wbr>i<wbr>&lt;=<wbr>5;<wbr>i ){</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

//<wbr>算法履行前的当时工夫</wbr>

start_time<wbr>=<wbr>System.currentTimeMillis();</wbr></wbr>

for(int<wbr>j<wbr>=<wbr>1;<wbr>j<wbr>&lt;=<wbr>test_data;<wbr>j ){</wbr></wbr></wbr></wbr></wbr></wbr></wbr>

testVar ;

testVar--;

}

//<wbr>算法履行后的当时工夫</wbr>

end_time<wbr>=<wbr>System.currentTimeMillis();</wbr></wbr>

//<wbr>打印一共履行工夫</wbr>

System.out.println("test_data<wbr>=<wbr>"<wbr><wbr>test_data<wbr><wbr>"\n"<wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

"Time<wbr>in<wbr>msec<wbr>=<wbr>"<wbr><wbr>(end_time<wbr>-<wbr>start_time)<wbr><wbr>"ms");</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

<wbr><wbr><wbr><wbr><wbr>//环后将循环次数加倍</wbr></wbr></wbr></wbr></wbr>

test_data<wbr>=<wbr>test_data<wbr>*<wbr>2;</wbr></wbr></wbr></wbr>

}

}

以上代码将别离核算出1000000、2000000、4000000...次的循环工夫。

缺陷：

?<wbr>不相同的平台履行的工夫不相同</wbr>

?<wbr>有些算法跟着输入数据的加大，测验工夫会变得不切实际！</wbr>

2．指令计数

指令---指编写算法的代码.对一个算法的完成代码核算履行指令次数。两种类型指令：不论输入巨细，履行次数永久不变；履行次数跟着输入巨细改动而改动。通常，咱们首要测验后一种指令。

例：核算指令履行次数

static<wbr>void<wbr>calculate_instruction(){</wbr></wbr>

long<wbr>test_data<wbr>=<wbr>1000;</wbr></wbr></wbr>

int<wbr>work<wbr>=<wbr>0;</wbr></wbr></wbr>

for<wbr>(int<wbr>i<wbr>=<wbr>1;<wbr>i<wbr>&lt;=<wbr>5;<wbr>i ){</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

int<wbr>count<wbr>=<wbr>0;<wbr></wbr></wbr></wbr></wbr>

for<wbr>(int<wbr>k<wbr>=<wbr>1;<wbr>k<wbr>&lt;=<wbr>test_data;<wbr>k ){</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

for(int<wbr>j<wbr>=<wbr>1;<wbr>j<wbr>&lt;=<wbr>test_data;<wbr>j ){</wbr></wbr></wbr></wbr></wbr></wbr></wbr>

//<wbr>指令履行次数计数</wbr>

count ;

work ;

work--;

}

}

System.out.println("test_data<wbr>=<wbr>"<wbr><wbr>test_data<wbr><wbr>"\n"<wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

"Instr.<wbr>count<wbr>=<wbr>"<wbr><wbr>count<wbr>);</wbr></wbr></wbr></wbr></wbr></wbr>

test_data<wbr>=<wbr>test_data<wbr>*<wbr>2;</wbr></wbr></wbr></wbr>

}

}

3．代数核算

代码1：

long<wbr>end_time<wbr>=<wbr>0;t1</wbr></wbr></wbr>

int<wbr>testVar<wbr>=<wbr>0;t2</wbr></wbr></wbr>

for<wbr>(int<wbr>i<wbr>=<wbr>1;<wbr>i<wbr>&lt;=<wbr>test_data;<wbr>i ){<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr>t3</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

testVar ;t4

testVar--;t4

}

假定t1<wbr>---<wbr>t4别离代表每条句子的履行工夫，那么，以上代码的总履行工夫为：t1<wbr><wbr>t2<wbr><wbr>n(t3<wbr><wbr>2t4).其间n<wbr>=<wbr>test_data,当test_data增大时，t1和t2可以忽略不计，也就是说，关于很大的n,履行工夫可以近似于：n(t3<wbr><wbr>2t4)</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

4．丈量内存运用率

一个算法中包括的目标和引证的数目，越多则内存运用越高，反之越低。

比拟增加率：

1.代数比拟法

条件1：c≦<wbr>f(n)/g(n)<wbr>≦<wbr>d<wbr>(其间c和d为正常数，n代表输入巨细)</wbr></wbr></wbr></wbr>

当满意以上条件1时，则f(n)和g(n)具有相同的增加率，或许两函数复杂度的阶相同！

如：f(n)<wbr>=<wbr>n<wbr><wbr>100<wbr><wbr>和<wbr><wbr>g(n)<wbr>=<wbr>0.1n<wbr><wbr>10两函数就具有相同的增加率。</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

条件2：<wbr>当n增大时，f(n)/g(n)趋向于0</wbr>

当满意此条件2时，则该两个增加函数有不相同的增加率。

比方：f(n)<wbr>=<wbr>10000n<wbr><wbr>20000<wbr><wbr>和<wbr><wbr>g(n)<wbr>=<wbr>n?2<wbr><wbr>n<wbr><wbr>1<wbr>。请咱们比拟以上两函数增加率能否相同，若是不相同，谁的增加率小？</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

2．大O表明法

若是f的增加率小于或许等于g的增加率，则咱们可以用如下的大O表明法：

f<wbr>=<wbr>O(g)</wbr></wbr>

O表明on<wbr>the<wbr>order<wbr>of</wbr></wbr></wbr>

将代码1的代数增加率函数用大O表达式如下：

f(n)<wbr>=<wbr>t1<wbr><wbr>t2<wbr><wbr>n(t3<wbr><wbr>2t4)</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

=<wbr>a1*n<wbr><wbr>a</wbr></wbr></wbr>

=<wbr>O(n)</wbr>

其间a1<wbr>=<wbr>t3<wbr><wbr>2t4;<wbr>a<wbr>=<wbr>t1<wbr><wbr>t2</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>

3．最佳、最差、均匀功能

对每一个算法不能只思考单一的增加率，而应该给出最佳、最差、均匀的增加率函数