|
|
发表于 2008-12-25 20:04:11
|
显示全部楼层
|阅读模式
来自 黑龙江省哈尔滨市
文章作者：duguyue100 [ESST]
信息来源：噩靈戰隊[Evil-Soul Security Team]（http://bbs.x-xox-x.com）
今天上午买了一本书，叫《算法设计与分析导论》，是三个台湾人写的，写的内容在我看来是相当的不错，基本上把算法的前沿和算法的精妙之处都写进去了，但是随之而来的就是一些比较专业的问题，比如多项式时间等等名词，我虽然读起来举步维艰，但是还是有乐趣在其中的。
下面先来看一下绪论，这个提纲挈领的东西，另外，这本书的其他的研究我还会陆续发出。
首先，算法重要吗？
有些人问了，什么叫算法，算法简单的来说就是解决问题的方法，在解决一个问题的时候，会有许多种方法供你选择，但是其中必然有一个是最优的，在执行过程中，虽然我们不可预料到其他有无不可抗拒性因素，但是我们知道在一个因素上的最优显然会造成整个问题解决起来更加的方便和利好。所以我们要讲就算法。
那么我们研究算法是为了什么呢？通常认为是进行高速的计算。如果一个高速计算的计算机执行了一个低效的算法的情况下，他的运行速度将不会超过在一个低速计算机上运行一个高效算法的时间长（我们这里说的高效和低效是相对来说的，不存在一个绝对高效的算法，也不存在一个绝对低效的算法，如果一个问题必须要用我们看来最低效的算法，这时在解决这个问题上它就是最高效的算法了）。
在我们这个生产力快速发展的社会，生产工具上可能没有什么大的差别，但是毫无疑问，我们必须提高个别生产率来在这场智力的赛跑中获胜。哪么怎样提高个别生产率呢？我们需要更好，更优的生产方法，而这种生产方法本身就是一种算法的实现，这也就是我们为什么要研究算法的原因了。
在绪论中，给出了一个实际的情况,就是在IBM SP2（一台超级计算机，曾经击败过象棋高手（汗！策略的硬度））和intel 486上分别实现插入排序和快速排序，结果的比较是，在数据量不超过400的情况下，IBM SP2凭借着优秀的计算量胜过了486，但是数据量一上去，那么IBM SP2就根本不行了。
这里说的是在生产工具中生产工具不相同的情况下算法能够发挥出的作用，但是在这个开放的社会，虽然还有一些技术保密的事情存在（事实上是大量存在的），但是在生产社会化的趋势愈加明显的时候，这种技术保密的手段就会日益趋向灭亡。之所以要说这些是因为要说明生产工具的优劣势其实可以假定为不存在了。那么可以预见，算法的优劣性将世界导致个别劳动生产率强弱的关系。下面我们就在插入排序和快速排序上做一些文章。看看算法的高低是怎样的关系。
我们首先生成10***00个数据，全部是逆序的，但是我们要进行从大到小排序，也就是说每个算法都是要进行他们最坏的时间复杂度（关于时间复杂度的问题以后会谈到）
首先，生成数据的PASCAL程序是这样的。（汗！俺是OIer，也就不写什么复杂语言的代码了） 复制内容到剪贴板
program sc;
var i:longint;//长整型
input,output:text;//文件类型
begin
assign(output,'c:/text.txt');//关联文件
rewrite(output);//建立文件
for i:=10***00 downto 1 do write(output,i,' ');//逆序写入数据
close(output);//关闭文件
end.这个代码可以生成10***00个逆序的数据（顺便说一下，电脑的运算速度到底有多快，其实说是几百万（古董级了吧），其实真正用于某个程序的运行并没有这么快，为什么呢？毕竟还是要进行别的运行操作，你们可以吧其中的for i:=10***00 downto 1 do write(output,i,' ');改成for i:=maxlongint downto 1 do write(output,i,' ');这样的话要运行很长的时间才能完，我等不了，所以按下了ctrl+break，但是这个时候，这些数据已经占了超过4GB的空间（看来就算是一堆数字还是非常牛的）maxlongint是多少呢？20亿，其实也不算很大，但是却运行了很长的时间，说明我们的电脑是心有余而力不足。）
我们下面开始写插入排序的程序。 复制内容到剪贴板
program ex;
const maxn=10***00;
var a:array[0..maxint] of longint;
i,j,k,n,s:longint;
input,output:text;
procedure inputtext;//读入数据过程
begin
assign(input,'c:/text.txt');
reset(input);
for i:=1 to maxn do read(a);//存储在数组中
close(input);
end;
procedure sort;//插入排序核心代码
var x:longint;
begin
for j:=2 to n do
begin
i:=j-1;
x:=a[j];
while (x<a)and(i>0) do
begin
a[i+1]:=a;
i:=i-1;
end;
a[i+1]:=x;
end;
end;//遍历并再次循环，确定插入数据位置
begin
inputtext;//调用过程
sort;//调用排序过程
assign(output,'shuchu.txt');
rewrite(output);
for i:=1 to 10***00 do
write(output,a,' ');//循环输出到文件
close(output);
end.这里是插入排序的代码，我测验过，在数据小的范围内确实是管用的，也就是说这个程序是有效的，那么这个程序跑了多长时间呢？至少5分钟，我不知道还有多久，因为我已经中断了它的运行。
这个排序的基本思想是进行循环搜索，决定下一个数据插入的位置，这样来达到目的，它的时间复杂度在最坏的情况下无疑是个天文数字，即使对于这个看起来并不大的10***00
下面是快速排序的代码： 复制内容到剪贴板
program ex;
var a:array[0..maxint] of longint;
i,j,k,n,s:longint;
input,output:text;
procedure inputtext;//读入数据
begin
assign(input,'c:/text.txt');
reset(input);
for i:=1 to 10***00 do read(input,a);
close(input);
end;
procedure sort(l,r:longint);//快速排序
var i,j,x,y:longint;
begin
i:=l;
j:=r;
x:=a[(l+r)div 2];//二分
repeat
while a<x do inc(i);
while x<a[j] do dec(j);
if i<=j then
begin
y:=a;
a:=a[j];
a[j]:=y;
inc(i);
dec(j);
end;
until i>j;//循环排序
if i<r then sort(i,r);
if l<j then sort(l,j);//两次递归，减少数量级，持续运用分治
end;
begin
inputtext;
sort(1,10***00);
assign(output,'c:/sc.txt');
rewrite(output);
for i:=1 to 10***00 do
write(output,a,' ');//循环输出，有可能在这里会浪费时间，但是排序过程绝对快
close(output);
end.这个程序我只是一瞬而过，就出来结果了，算法在这里突出的重要性已经出来了，就是时间的快慢！
我们说评价一个算法是由多方面来计算的，但是在这个科技发达的社会，空间的消费通常被我们当作一个比较不重要的东西，因为既然要处理大数据，那么空间基本就能够得到保证，所以最终要的就是归结到时间的问题上！
在我们比社会平均劳动生产率快的时候，我们才能得到更多的利润和机会！
下面开始讲一下时间复杂度的简单判定，判定一个是否能用相对高效的算法来解决的根本途径是用数学的方法验证是一个具有多项式时间的算法，简单的说就是一个能否用∑来列出通项公式的问题。如果能够列出，我们就可以找到一个比较有效的算法，如果不能，那么我们只能考虑那些小范围不会让我们头痛，但大数据绝对会让我们吃惊的算法了。上述观点大概就是NP完全性理论（这套理论比较硬，我还没看，据说是大学中最不好理解的地方了）
上一段作为本贴的收尾的话，显然显得有些累赘和困难，但是我为了进行数学探索不得不这样做了，大家应当尽量看懂，初高中的学生们要好好理解一下数列这一章的内容，顺便说一下，有些地方我以后可能会说的不好，因为我还是个高中生。所以大家如果不懂可以来问我，或者我给定义大家去找牛人问把。 |
|
