如何分析算法的时间复杂度?

分析一个算法的时间复杂度有两种情况可以分析
1.写完之后看执行时间(事后分析估算方法:)
2.分析算法函数,得出算法时间复杂度(事前分析估算方法:)

事后分析估算方法:

比较容易想到的方法就是我们把算法执行若干次,然后拿个计时器在旁边计时,这种事后统计的方法看上去的确不 错,并且也并非要我们真的拿个计算器在旁边计算,因为计算机都提供了计时的功能。这种统计方法主要是通过设 计好的测试程序和测试数据,利用计算机计时器对不同的算法编制的程序的运行时间进行比较,从而确定算法效率 的高低,但是这种方法有很大的缺陷:必须依据算法实现编制好的测试程序,通常要花费大量时间和精力,测试完 了如果发现测试的是非常糟糕的算法,那么之前所做的事情就全部白费了,并且不同的测试环境(硬件环境)的差别 导致测试的结果差异也很大。

事前分析估算方法:

很多时候,我们并不在算法实现之后再来对算法进行估算,我们需要在编写之前就对我们的算法进行估算。经过总结,我们发现一个高级语言编写的程序程序在计算机上运行所消耗的时间取决于下列因素:

算法分析:
由此可见,抛开这些与计算机硬件、软件有关的因素,一个程序的运行时间依赖于算法的好坏和问题的输入规模。
如果算法固定,那么该算法的执行时间就只和问题的输入规模有关系了。

那么再次以之前的求和案例为例,进行分析。
需求:计算1到100的和。
解法1:

解法2:

因此,当输入规模为n时,第一种算法执行了1+1+(n+1)+n=2n+3次;第二种算法执行了1+1+1=3次。如果我们把 第一种算法的循环体看做是一个整体,忽略结束条件的判断,那么其实这两个算法运行时间的差距就是n和1的差距。

为什么循环判断在算法1里执行了n+1次,看起来是个不小的数量,但是却可以忽略呢?我们来看下一个例子:

需求: 计算100个1+100个2+100个3+…100个100的结果
代码:

上面这个例子中,如果我们要精确的研究循环的条件执行了多少次,是一件很麻烦的事情,并且,由于真正计算和
的代码是内循环的循环体,所以,在研究算法的效率时,我们只考虑核心代码的执行次数,这样可以简化分析。

我们研究算法复杂度,侧重的是当输入规模不断增大时,算法的增长量的一个抽象(规律),而不是精确地定位需要 执行多少次,因为如果是这样的话,我们又得考虑回编译期优化等问题,容易主次跌倒。

我们不关心编写程序所用的语言是什么,也不关心这些程序将跑在什么样的计算机上,我们只关心它所实现的算
法。这样,不计那些循环索引的递增和循环终止的条件、变量声明、打印结果等操作,最终在分析程序的运行时间
时,最重要的是把程序看做是独立于程序设计语言的算法或一系列步骤。我们分析一个算法的运行时间,最重要的
就是把核心操作的次数和输入规模关联起来。

如何分析算法的时间复杂度?

0

算法的效率分析因子

概念:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>0,f(n)总是比g(n)大,那么我们说f(n)的增长渐近 快于g(n)。

概念似乎有点艰涩难懂,那接下来我们做几个测试。

1.测试一:假设四个算法的输入规模都是n:

那么,上述算法,哪一个更快一些呢?

算法的效率分析因子
算法的效率分析因子
通过数据表格,比较算法A1和算法B1: 当输入规模n=1时,A1需要执行5次,B1需要执行4次,所以A1的效率比B1的效率低; 当输入规模n=2时,A1需要执行7次,B1需要执行7次,所以A1的效率和B1的效率一样; 当输入规模n>2时,A1需要的执行次数一直比B1需要执行的次数少,所以A1的效率比B1的效率高; 所以我们可以得出结论

当输入规模n>2时,算法A1的渐近增长小于算法B1 的渐近增长 通过观察折线图,我们发现,随着输入规模的增大,算法A1和算法A2逐渐重叠到一块,算法B1和算法B2逐渐重叠
到一块,所以我们得出结论:

随着输入规模的增大,算法的常数操作可以忽略不计

2.测试二:假设四个算法的输入规模都是n:

那么上述算法,哪个更快一些?
算法的效率分析因子

通过数据表格,对比算法C1和算法D1:
当输入规模n<=3时,算法C1执行次数多于算法D1,因此算法C1效率低一些;
当输入规模n>3时,算法C1执行次数少于算法D1,因此,算法D2效率低一些,
所以,总体上,算法C1要优于算法D1.

通过折线图,对比对比算法C1和C2: 随着输入规模的增大,算法C1和算法C2几乎重叠
通过折线图,对比算法C系列和算法D系列: 随着输入规模的增大,即使去除n^2前面的常数因子,D系列的次数要远远高于C系列。

因此,可以得出结论:
随着输入规模的增大,与最高次项相乘的常数可以忽略

3.测试三:假设四个算法的输入规模都是n:

算法的效率分析因子

算法的效率分析因子

通过数据表格,对比算法E1和算法F1:
当n=1时,算法E1和算法F1的执行次数一样;
当n>1时,算法E1的执行次数远远小于算法F1的执行次数;
所以算法E1总体上是由于算法F1的。

通过折线图我们会看到,算法F系列随着n的增长会变得特块,算法E系列随着n的增长相比较算法F来说,变得比较 慢,所以可以得出结论:

最高次项的指数大的,随着n的增长,结果也会变得增长特别快

4.测试四:假设四个算法的输入规模都是n:

假设五个算法的输入规模都是n:

那么上述算法,哪个效率更高呢?
算法的效率分析因子
算法的效率分析因子

通过观察数据表格和折线图,很容易可以得出结论:
**算法函数中n最高次幂越小,算法效率越高 **

总上所述,在我们比较算法随着输入规模的增长量时,可以有以下规则:

  1. 算法函数中的常数可以忽略;
  2. 算法函数中最高次幂的常数因子可以忽略;
  3. 算法函数中最高次幂越小,算法效率越高。
0

数据结构的分类方式

传统上,我们可以把数据结构分为逻辑结构物理结构两大类。

1、逻辑结构分类:

逻辑结构是从具体问题中抽象出来的模型,是抽象意义上的结构,按照对象中数据元素之间的相互关系分类。
a.集合结构:集合结构中数据元素除了属于同一个集合外,他们之间没有任何其他的关系。
数据结构分类
b.线性结构:线性结构中的数据元素之间存在一对一的关系
数据结构分类
c.树形结构:树形结构中的数据元素之间存在一对多的层次关系
数据结构分类
d.图形结构:图形结构的数据元素是多对多的关系
数据结构分类

2、物理结构分类:

逻辑结构在计算机中真正的表示方式(又称为映像)称为物理结构,也可以叫做存储结构。常见的物理结构有顺序存储结构、链式存储结构。

顺序存储结构:
把数据元素放到地址连续的存储单元里面,其数据间的逻辑关系和物理关系是一致的 ,比如我们常用的数组就是 顺序存储结构。

数据结构分类

链式存储结构:
顺序存储结构存在一定的弊端,就像生活中排时也会有人插队也可能有人有特殊情况突然离开,这时候整个结构都
处于变化中,此时就需要链式存储结构。

链式存储结构是把数据元素存放在任意的存储单元里面,这组存储单元可以是连续的也可以是不连续的。此时,数据元素之间并
不能反映元素间的逻辑关系,因此在链式存储结构中引进了一个指针存放数据元素的地址,这样通过地址就可以找
到相关联数据元素的位置
数据结构分类

0