算法起引

文档状态：编辑....

设计的魅力在于能让人在枯燥中感受快乐

Table of Contents

前言

本来我是不想写关于算法类的介绍的,原因很简单,我不想分享知识,这不是自私的原因,而是懒得去做,设计本身就是很复杂的东西,设计一个算法就像是在微分方程一样,没有固定的解法,不一定有解法[可计算性],但是如果仅仅是为了结果去设计,人总会陷入漫长的枯燥中,真正的设计者享受着设计的每一个过程,像是认真捏造一个细碎的星星,企图窥探银河的壮观,那是一种特殊的感受,无法用语言描述,总而言之很壮观,很美丽,那么到底是什么驱动了我的书写,一个是知识的系统化,另一个是来自开源社区的共享精神,可以说互联网思维吧笑：),但愿每一个看过这些东西的算法爱好者能感受其中的魅力,自认为在抒情方面的语言组织能力不够好,所以废话不多说。

什么是算法

满足以上特性的叫做算法.

有限是指算法中的指令不能是没有边界的数量,没有边界就像死循环一样,如何让产生答案.如果一个算法缺少有限性只能叫做计算方法.
确定性是指每一个基本步骤必须是无歧义的,不能出现让执行机器为难的事情，程序语言就是用来干这个的.
输入 0个输入或多个输入
输出 至少一个输出
可行性 运算的基本指令单位必须是充分的基本的,比如你直接写一个函数求解常微分方程这就有点不合适了

以上仅仅是基本的需求,在这些需求出现了之后,人开始发现,条条大路通罗马,一个问题有很多的解决方案,这么多方案哪个最好呢？就像是选美大赛,选美肯定有一定的标准,所以算法的比较也一定有自己的标准,标准很简单,时间复杂度与空间复杂度,鉴于硬件容量的迅猛发展,人们更倾向于时间复杂度,将其作为计算机世界的货币,无论是时间复杂度还是空间复杂度都可以被量化为performance,很多人把所有的赞誉都给了时间复杂度,其实如果不是空间复杂度的割肉,怎会在时间上取得那么多的好效果,自从得到了货币,有些人开始想着去购买东西,购买其他性能,购买其他功能,这不过是一场权衡的游戏,看谁能在context下做出更好的决策罢了.

数学化描述

数学不好的可以绕行
按特性描述算法,果然不严谨,老师说过的既要有数学家的严谨又要有工程师的直觉,这句话果然很重要,作为数学的基石,不用集合描述都感觉是在浪费。
定义一个四元组 ($(Q,I,\Psi,f)$)
满足以下条件:
Q代表计算状态
I代表输入
$(\Psi)$代表输出
$(f)$代表计算规则
$(I\subset Q,\Psi\subset Q)$
$(\forall x_i \in \Psi,f(x_i)=x_i)$
对$(I)$中的任意一个x定义一个计算序列$(x_1,x_2,x_3...x_k)$
$(如果 k 是满足 f(x_k)\in \Psi 的最小值,那么必然存在f(x_k+n)=f(x_k))$

限制
$(\Psi)$不为空
$(f)$是基本充分的

降低时间复杂度

    #有时间一定码上Orz=3

图书推荐

算法导论.第三版