数据结构和算法的关系:

好比是梁山伯与祝英台罗密欧与朱丽叶,两者是不可分割的关系.

1 算法的定义:

解决特定问题的求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作,每一个操作都完成特定的功能.

2 算法的5个特性:

输入输出:

具有0个或多个输入,(输入参数可以是0个)
一定要输出,否则该算法无意义.

有穷性:

指算法在执行有限的步骤后,自动结束而不是出现无限循环,并且每一个步骤在可接受的时间内完成.

步骤有限
不会无限循环
每一个步骤完成的时间有限.

确定性:

算法的每一个步骤都具有确定的意义

算法在一定条件下,只有一条执行路径,对比程序图作比较.

可行性:

算法的每一个步骤都必须是可行的,即每一步都能够通过执行有限的次数完成.

3 算法设计的要求

正确性:
至少应该具有输入输出和加工处理无歧义性,能正确反映问题的需求能够得到问题的正确答案.

算法程序没有语法错误;

算法程序对于合法的输入能够产生满足要求的输出结果:

算法程序对于非法的输入能够给出满足规格说明的结果.

类比实际工作中,接口返回的数据必须有非真的处理,同样我们在编写代码时,if–else一定要成对出现.

可读性:

算法设计的另一目的是为了便于阅读理解和交流.

这就是为什么需要代码注释.

健壮性:

当输入的数据不合法时,算法也能做出相关处理,而不是产生异常或莫名奇妙的结果.

时间效率高和存储质量低:

时间效率指的是:算法的执行时间.
存储需求:算法在执行过程中需要的最大存储空间,包括占用的内存或外部硬盘存储空间.

4 算法效率的度量方法分析:

主要分为事后统计方法和事前分析估算方法.

前者一般不考虑,一般着重使用后者.

``
-(void)sumFenxi
{
//算法1

int i= 0, sum1 = 0 ,n = 100;  //执行了1次
for (i = 1; i <= n; i++) {
    sum1 = sum1 + 1;          //执行了n+1次
}
NSLog(@"sum == %d",sum1);     //执行了1次

}

-(void)sumFenxi2
{
//算法2

int  sum2 = 0 ,n2 = 100;      //执行了1次
sum2 = (1 + n2) * n2 / 2;      //执行了1次
NSLog(@"sum == %d",sum2);      //执行了1次

}

-(void)sumFenxi3
{
//算法3

int i= 0, x = 0 , sum = 0, n = 100;  //执行了1次
for (i = 1; i <= n; i++) {
    for (int j = 0; j<= n ; j++) {
        x++;
        sum = sum + x;
    }          //执行了n * n次
}

NSLog(@"sum == %d ",sum); //执行了1次

}
``

得出的表格是:

次数	算法A(n+1+1)	算法B(1+1+1)	算法C(n*n + 1 + 1)
n=1	3	3	3
n=2	4	3	6
n=3	5	3	27
n=10	12	3	102
n=100	102	3	10002

从而得出函数的渐进增长:
给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么,我们说f(n)的增长渐进快于g(n).
类比数学函数上是,斜率大,则y值增长的越快.
常数可以忽略掉,即算法A (n),算法B (1),算法C (n*n).

接下来看下图:

次数	算法A(4n+8)	算法A’(n)	算法C(nn2 + 1 )	算法C’(n*n)
n=1	12	1	3	1
n=2	16	2	9	4
n=3	20	3	19	9
n=10	48	10	201	100
n=100	408	100	2 0001	1 0000

综上可得:

判断一个算法的效率时,函数中的常熟和其他次要项尝尝可以忽略不计,而只关注最高阶项的阶数.

某个算法,随着n的增大,他会越来越优于另一算法,或者越来越差于另一算法.

5 算法时间复杂度

定义:在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级,算法的时间复杂度,也就是算法的时间量度,记作:T(n) = O(f(n)).表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度.

一般随着n的增大,T(n)增长最慢的算法为最优算法.
之前的3个求和算法的时间复杂度为O(n),O(1),O(n*n).分别称为线性阶,常数阶,平方阶.

6 推到无穷大O阶的方法

用常数1取代运行时间中的所有加法常数
在修改后的运行次数函数中,只保留最高阶项.
如果最高阶项存在且不是1,则去除与这个项相乘的常数
最后得到大O阶.

7 常见的时间复杂度

8 算法的平均情况和最坏情况

举例说明,在n个随机数字数组里查找某个数字,最好的情况是取得第一个就是我们要找的,最坏的情况是一直取到最后一个才取到,前者的时间复杂度为O(1),后者的时间复杂度为O(n).而通过我们前面的学习,我们知道这种情况的时间复杂度就是O(n).

平均运行时间是所有情况中最优意义的,因为他是期望运行的.
计算所有情况的时间复杂度的平均值为平均时间复杂度
计算最坏情况下的时间复杂度为最坏时间复杂度.

9 算法的空间复杂度

定义:
通过计算算法所需的存储空间实现,计算公式为:S(n) = O(f(n)).

一般求时间复杂度指的就是:时间复杂度.