算法(algorithm)

原创
2011/08/17 13:15
阅读数 427

算法(algorithm)

对一个现有的问题我们采取的解决过程及方法,可简单可复杂,可高效可低效。一个用算法实现的程序会耗费两种资源:处理时间和内存。很显然,一个好的算法应该是耗费时间少、所用内存低,但是,在实际中,我们往往不能两方面顾全!

算法的效率分析标准:

衡量算法是否高效主要是从以下几个方面来分析:

¨ 简单性和清晰度

一般我们都希望算法越简单越清晰就越好,但是要保证效率为前提。可是,往往我们在复杂的项目开发中所遇见的问题比较复杂,对时间和空间效率的要求也较高,因此,算法一般都会比较复杂。

¨ 空间效率

注意:这里的空间效率并不是指算法代码占用的内存指令空间,而是指代码中的数据分配(变量与变量所引用值的分配)以及方法调用所使用的内存(调用栈的空间分配)。比如,我们常用的递归,虽然会使代码清晰简单,但是内存的使用也会大大提高。理想的,程序所使用的内存应该和数据及方法调用 所占用内存相等。但事实总是会有些额外的开销!因此,空间效率也是我们衡量算法的方面之一。

¨ 时间效率

针对同一任务所使用的不同算法所执行的时间都会不同。

比如:在一个数据集合中查找数据,我们会从第一个数据开始查找,一直找到需要的数据为止,如果查找数据存在,则这种查找方式(称之为线性查找)一般要查找半个列表!然而,如果数据的排放是有序的,则通过另一种查找方法会更有效,即二分查找法,首先从集合的中间开始,如果查找值在中间值的前面,则从集合的前一半重复查找,否则从后一半查找,每执行一次则将查找的集合减少为前一次的一半。

算法的类型:

所有的算法可以大概分为以下三种类型:

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;

}

}

以上代码将分别计算出100000020000004000000...次的循环时间。

缺点:

Ø 不同的平台执行的时间不同

Ø 有些算法随着输入数据的加大,测试时间会变得不切实际!

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增大时,t1t2可以忽略不计,也就是说,对于很大的n,执行时间可以近似于:n(t3 + 2t4)

4.测量内存使用率

一个算法中包含的对象和引用的数目,越多则内存使用越高,反之越低。

比较增长率:

1.代数比较法

条件1c≦ f(n)/g(n) ≦ d (其中cd为正常数,n代表输入大小)

当满足以上条件1时,则f(n)g(n)具备相同的增长率,或者两函数复杂度的阶相同!

如:f(n) = n + 100  和  g(n) = 0.1n + 10两函数就具备相同的增长率。

条件2: 当n增大时,f(n)/g(n)趋向于

当满足此条件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.最佳、最差、平均性能

对每一个算法不能只考虑单一的增长率,而应该给出最佳、最差、平均的增长率函数

展开阅读全文
打赏
0
5 收藏
分享
加载中
更多评论
打赏
0 评论
5 收藏
0
分享
返回顶部
顶部