一些常见的算法,我会写出对应的Java写法,并且一些常见的源码解析 如HashMap等 ,我会在后期着重在Java部分中讲解,在这部分我们更加着重于理解算法与数据结构中的原理与思想,编程语言尽管存在差异,但是并不会造成太大的阅读障碍,如果你有Java或者C#等的基础,读起来基本不会存在太大的语言障碍,同时学习C++中例如指针的知识,更会让我们体会到指针的优越以及麻烦之处,阅读前可以简单补充一些C++基础语法(本篇基本不需要)
公司开发一个客服电话系统,小菜需要完成客户排队模块的开发,经过三次修改:
第一次:小菜使用了数据库设计了一张客户排队表,并且设置了一个自动增长的整型id字段,来一个用户,就在这张表的末尾插入一条数据,等客服系统一空闲,就将表中最前的的客户提交,然后删除这条记录。
第二次:小菜用数组变量重新实现了这个功能,害怕数组不够大,选择远大于实际情况的100作为数组长度
第三次:小菜使用了数据结构中的 “队列结构” 终于满足了需求
说明:此例子归纳参考自《大话数据结构》
来看一个问题:
公元前五世纪,我国古代数学家张丘建在《算经》一书中提出了“百鸡问题”:鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一。百钱买百鸡,问鸡翁、鸡母、鸡雏各几何?请设计一个“高效”的算法求解。
也就是说:
买一只公鸡要五文,买一只母鸡要三文,而一文可以买三只小鸡,共有100文,问公鸡母鸡小鸡各能买几只?
话不多说,我们先给出一种最容易想到的方式,也就是列两个三元方程组
也就是满足鸡的总数为100,同时花钱数也为100,我们来看一下代码实现
方式一:
//i j k 分别代表公鸡 母鸡 雏鸡的数量
//20、34、300 为100元最多能买公鸡、母鸡、小鸡的数量
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 34; j++) {
for (int k = 0; k < 300; k = k + 3) { //k = k + 3 是为了满足小鸡实际存在的要求
if (5*i + 3*j + k/3 == 100 && i + j + k == 100) {
cout << "公鸡 母鸡 雏鸡 数量分别为:" << i <<", "<< j <<", "<< k << endl;
}
}
}
}
我们用了三层循环,有没有办法能简化以下代码呢?能不能减少循环层数呢?这显然是可行的,上面小鸡的数量这一层明显可以省略的,因为总数是已知的
方式二:
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 34; j++) {
k_temp = 100 - i - j;
if (k_temp % 3 == 0)
k = k_temp;
if (5*i + 3*j + k/3 == 100 && i + j + k == 100) {
cout << "公鸡 母鸡 雏鸡 数量分别为:" << i <<", "<< j <<", "<< k << endl;
}
}
}
确实程序更加优化了一些,但是这样是不是就可以了呢?其实还可以优化为一层循环!
方式三:
int i, j, k, t;
for (int t = 0; t <= 25/7; t++) {
i = 4 * t;
j = 25 - 7 * t;
k = 75 + 3 * t;
cout << "公鸡 母鸡 雏鸡 数量分别为:" << i <<", "<< j <<", "<< k << endl;
}
上例中对程序的优化涉及到了数学的运算
//根据花钱的总数为100列式
5x + 3y + (100 - x - y)/3 = 100
//对上式进行化简
y = 25 -(7/4)x
= 25 - 2x + x/4
//设 x/4 = t,原式子可变为
y = 25 - 7t
//可以得到三个不等式
x = 4t >= 0
y = 25 - 7t >= 0
z = 75 + 3t >= 0
//解得
t >= 0
t <= 25/7
为了增加说服力,我们测试每一个程序的运算时间,不太熟悉的朋友我下面已经贴出了代码
#include<ctime>
clock_t startTime,endTime;
startTime = clock();
......测试代码
endTime = clock();
cout << "The run time is: " << (double) (endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
我们将数据放大一些,方便体现差异,我们将总金额和总数量均改为1000 下面是三种方式的运算时间
The run time is: 0.114s
The run time is: 0.03s
The run time is: 0.026s
很显然程序逐步的到了优化,减少了for循环 大大的减少了循环次数,所以节省了时间
想要回答这个问题,我们先开看一下数据结构和算法的概念
数据结构是指相互之间存在一种或多种特定关系数据元素的集合
也就是说,计算机在对数据进行存储的时候并不是杂乱无序的而是拥有一定规则的,一个或多个数据元素之间拥有一定的相互关系,所以也可以说数据结构是计算机存储和组织数据的方式
算法是一种可以被计算机使用来解决问题的的方法,这种方法也正是解决问题的具体步骤
对于小型的程序而言,即使这个算法比较差劲,解决问题的步骤比较累赘繁琐,也不会有很大的关系,只要能解决问题的就是好程序,但是如果对于数据量较大的中大型程序,我们就需要对方法的时间和空间进行有效的利用,也就是设计一个高效的算法,在同样硬件设备的情况下,有时候甚至可以将速度提高十倍甚至百倍
数据结构是对计算机所存储的数据之间的一种组织管理,算法是对数据进行操作从而将你解决问题的方法在计算机中具体实现,也就是说,在计算机中而言,其实这两者单独拿出来讨论是没有什么实际意义的,就像鱼离不开水一样,即使一个优秀的算法,如果数据之间没有任何结构关系可言,算法也就无从实现,也就没有意义了,而即使数据之间有了组织关系,但是不对其进行操作这显然也没有意义。
简单总结:只有数据结构的程序是没有灵魂的,只有算法的程序却只有魂魄,没有躯体
不可否认,数据结构是非常重要的,但我更加倾向于算法为核心,正如 Algorithms(4th.Edition) 中的观点,数据结构是算法的副产品或者结果,在我看来,如何建立一个有效且高效的算法以及模型是更重要一些的,开发的最终目的就是通过程序利用科技设备实现我们实际生活中的一些需求,我们遇到问题的第一步都是在现实中对问题进行分析,然后设计出合适的方法,然后就要想办法将这种方法表达给计算机设备,但是这个时候就需要数据结构这样一种满足需要的产物,来支持我们对我们的设备具体表达我们的方法,尤其随着数据量的检验,不同的算法就会对解决实际问题的效率产生更大的影响,我用一个不是很恰当却很形象的例子表达就是:你的身体(数据结构)死了,你可能还活着,但你的灵魂(算法)死了,你即使活着也已经死了
当然数据结构的重要性也是不容置疑的,一个好的数据结构,可以帮助我们的程序更加高效,如果什么时候,模型以及算法的选用已经可以根据数据的特点以及需求选用,我们就可以将更多的精力投入到数据结构的设计中去,不过这也仅仅是一种美好的假想,所以我们还是要学好算法,但是学好算法,我们也就要对支持我们算法的数据结构进行一定的研究
说了一些个人的观点,那让我们赶紧介绍一些入门的必备知识
逻辑结构:数据对象中数据元素之间的相互关系
① 集合结构:数据元素之间的唯一关系就是属于同一个集合
② 线性结构:数据元素之间存在一对一的关系(除首尾元素均存在前驱和后继)
③ 树形结构:数据元素之间存在一对多的关系
④ 图形结构:数据元素之间存在多对多的关系
物理结构:数据的逻辑结构关系在计算机中的存储形式
① 顺序存储结构:把元素分别放在地址连续的存储单元中的存储方式
② 链式存储结构:把元素存储在任意的存储单元中的存储方式
③ 散列 (哈希) 存储方式:是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术
④ 索引存储方式:存储时,除了存储节点,还附加建立了索引表来表示节点的地址
次数 | A:2n+4 | B:3n+3 | C:2n | D:3n |
---|---|---|---|---|
n=1 | 6 | 6 | 2 | 3 |
n=2 | 8 | 9 | 4 | 6 |
n=3 | 10 | 12 | 6 | 9 |
n=10 | 24 | 33 | 20 | 30 |
n=100 | 204 | 303 | 200 | 300 |
n = 1的时候 算法 A 和 B 的效率一致,但是从n = 2的时候开始算法 A 的效率已经大于算法 B 了,n值变大后,算法 A 相比 B 变的更加快速
函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n > N,f(n)总是比g(n)大,那么,我们说f(n)的渐近增长快于g(n)
次数 | A:2n+6 | B:3n²+3 | C:n | D:n² |
---|---|---|---|---|
n = 1 | 8 | 6 | 1 | 1 |
n = 2 | 10 | 15 | 2 | 4 |
n = 3 | 12 | 30 | 3 | 9 |
n = 10 | 26 | 303 | 10 | 100 |
n = 100 | 206 | 30003 | 100 | 10000 |
算法 A 和 B 比较的时候,n = 1的时候 B效率更高,从n = 2开始 算法 A 就比较高效,随着数据的输入,体现的越明显,但是我们同时将这两个算法去掉最高次项的系数,接着可以看到对数据的走向仍然影响不大
算法的时间复杂度是一个函数 T(n),它定性描述该算法的运行时间,通常用大O表示法,记作:T(n) = O(f(n)) 例如3n² + 2n + 1 的时间复杂度为 O(n²)
注意:
O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) < O(n^n)
实际开发中,我们常见到的还是前几个加粗的
我们还需要提到两个概念:
最坏情况与平均情况
最坏情况就是,运行时间的最大值,情况不能再坏了
平均时间就是
一般情况下,我们都是指最坏时间复杂度,但平均时间是最有意义的时间,因为它与我们的期望值更接近
这些文章,当然谈不上算什么有深度的技术,但是我在尽可能的将一些概念通过举例、图表等方式给对这方面知识有需要的朋友,快速的入门,通过一些通俗的说法,先对一些知识有一定的了解,在此基础上,去看一些深入的权威书籍,或者大牛的博文,就会不至于劝退,自知技术有限,但仍然想给一些刚刚接触这部分知识的朋友们一些帮助,总得一个人,经历一些难捱的日子,你才会变得更加强大!
如果文章中有什么不足,或者错误的地方,欢迎大家留言分享想法,感谢朋友们的支持!
邮箱:ideal_bwh@163.com