目录
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
数据结构包括数据的逻辑结构、数据的存储结构以及数据的运算
按照某种逻辑关系组织起来的一批数据,按一定的方式把它存放在计算机的内存里,在这个基础上为了实现某个功能(比如查找某个元素,删除某个元素,给所有元素排序等等)而进行的一些列操作,我们把这一些列的操作步骤描述出来就是算法。
算法也可以解释为:计算机求解一个问题所需的一系列步骤。
时间复杂度:是用程序执行的次数来衡量,不是程序执行的时间。
空间复杂度:用程序执行所需要的最大内存。
a不等于1)a^x=N,那么数x叫做以a为底N的对数(logarithm),记作x=logaN。其中,a叫做对数的底数,N叫做真数。
基本操作执行次数
关于代码的基本操作执行次数,我们用四个生活中的场景,来做一下比喻:
场景1:给小灰一条长10寸的面包,小灰每3天吃掉1寸,那么吃掉整个面包需要几天?
答案自然是 3 X 10 = 30天。
如果面包的长度是 N 寸呢?
此时吃掉整个面包,需要 3 X n = 3n 天。
如果用一个函数来表达这个相对时间,可以记作 T(n) = 3n。
场景2:给小灰一条长16寸的面包,小灰每5天吃掉面包剩余长度的一半,第一次吃掉8寸,第二次吃掉4寸,第三次吃掉2寸......那么小灰把面包吃得只剩下1寸,需要多少天呢?
这个问题翻译一下,就是数字16不断地除以2,除几次以后的结果等于1?这里要涉及到数学当中的对数,以2位底,16的对数,可以简写为log16。
因此,把面包吃得只剩下1寸,需要 5 X log16 = 5 X 4 = 20 天。
如果面包的长度是 N 寸呢?
需要 5 X logn = 5logn天,记作 T(n) = 5logn。
算法问题实质上就是数学问题,计算时间复杂度和空间复杂度远远没这么简单!
给定一个数集A,假设其中的元素为x。现对A中的元素x施加对应法则f,记作f(x),得到另一数集B。假设B中的元素为y。则y与x之间的等量关系可以用y=f(x)表示。我们把这个关系式就叫函数关系式,简称函数。函数概念含有三个要素:定义域A、值域C和对应法则f。其中核心是对应法则f,它是函数关系的本质特征。
初等数学研究的对象是不变的量,高等数据研究的对象是变动的量。比如极限。
“极限”是数学中的分支——微积分的基础概念,广义的“极限”是指“无限靠近而永远不能到达”的意思。极限是一种“变化状态”的描述。此变量永远趋近的值A叫做“极限值”
在数学中,对数是对求幂的逆运算,正如除法是乘法的倒数,反之亦然。
如果a的x次方等于N(a>0,且
场景3:给小灰一条长10寸的面包和一个鸡腿,小灰每2天吃掉一个鸡腿。那么小灰吃掉整个鸡腿需要多少天呢?
答案自然是2天。因为只说是吃掉鸡腿,和10寸的面包没有关系 。
如果面包的长度是 N 寸呢?
无论面包有多长,吃掉鸡腿的时间仍然是2天,记作 T(n) = 2。
场景4:给小灰一条长10寸的面包,小灰吃掉第一个一寸需要1天时间,吃掉第二个一寸需要2天时间,吃掉第三个一寸需要3天时间.....每多吃一寸,所花的时间也多一天。那么小灰吃掉整个面包需要多少天呢?
答案是从1累加到10的总和,也就是55天。
如果面包的长度是 N 寸呢?
此时吃掉整个面包,需要 1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n。
记作 T(n) = 0.5n^2 + 0.5n。
上面所讲的是吃东西所花费的相对时间,这一思想同样适用于对程序基本操作执行次数的统计。刚才的四个场景,分别对应了程序中最常见的四种执行方式:
场景1:T(n) = 3n,执行次数是线性的。
//TODO
场景2:T(n) = 5logn,执行次数是对数的。
//TODO