作为一个iOS开发者，其实是很少用到算法的，但是算法是计算机运算的基础，虽然我们平时开发中很少使用，但是想要对软件开发有更加深入的研究，那么必须要了解一下算法，了解算法，我们可以知道程序的最佳运行效率，还可以知道我们程序是否高效
许多朋友其实是不知道我们写的程序的运行效率的（包括我，在今天之前也是不知道的）,今天就让我们首先学习一下怎么知道我们程序的运行效率。
算法效率的度量方法
我们常说设计算法要提高效率，但是我们怎么来知道我们的算法效率是多少呢，有两个最常见的方法
- 1、利用记时功能，我们写几个算法，然后用计时器对不同的算法编程运行，进行时间比较，从而确定算法效率的高低
这个其实有一点不怎么靠谱，首先即使能够比较出来哪种算法比较快，但是我们还是不清楚为啥这种算法会快一点；其次现在CPU运行效率都比较快，如果是几百几千很有可能根本就区分不出来。所以这种方法基本排除了
- 2、事前估算，在程序运行之前，运用统计的方法对算法进行估算，这种还是比较准确的
一个高级程序语言编写的程序在计算机运行所消耗的时间取决于一下几点
- 1、算法采用的方法
- 2、编译产生的代码量
- 3、问题的输入规模
- 4、机器执行指令的速度
第一条是算法好坏的根本，第二条由软件决定，第四条由硬件性能决定，抛开硬件与软件因素，决定一个算法效率的因素是算法采用的方法和问题的输入规模问题的输入规模
现在我们就举三个例子来说明一下问题
E35F2694-9962-474B-9DB5-8BAA2493BE8E.png
首先我们先看前两种算法，其实他们的效果都是一样的，都是计算从1加到100的值，但是第一种算法执行了n+2次，而第二种算法执行了3次。算法效率不用比都知道是哪一种的效率高了。
我们在来对三种算法进行比较，发现其实三种算法效率的高低主要是由核心也就是中间部分决定，我们去掉相同的部分，可以看到
f(n)1 = n
f(n)2 = 1
f(n)3 = n*n
随着n的增大，他们之间的效率相差也是越大。
到这里，我们来介绍一下这篇文章的核心概念算法时间复杂度
概念：在进行算法分析的时候，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。算法时间复杂度，也就是算法的时间度量，记着：
T(n) = O (f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作为算法渐进时间复杂度，简称时间复杂度
这样大写OO()来体现算法时间复杂度的记法，我们称作为大O记法
由此时间复杂度的记法的定义可知我们上面的三种算法的时间复杂度分别为O(n) O(1) O(n* n)。其中O(1)叫常数阶，O(n)叫线性阶，O(n* n)叫平方阶
推导大O记法
- 1、用常数1来取代运行时间中所有的加法常数
- 2、在修改后的运行次数函数中，只保留最高阶
- 3、如果最高阶项存在但不是1，去除最高阶相乘的常数
一些时间复杂度解释
EDFCCA98-3700-4EF2-8112-EB5E051A3C30.png
时间复杂度所消耗的时间排序
0(1)<O(logn)<O(n)<O(nlogn)<0(n2 ) <0(n3 ) <0(2")<O(n!)<O(nn)
结束语
很多程序猿做了很多年的编程，但是还是不怎么清楚算法的时间复杂度的估算，其实这是一个很可悲的事情，因为弄不清楚算法时间复杂度，所以也就从来不深究自己写代码的效率是否低下。
有一些人经常给自己的借口是，现在CPU越来越快，不怎么需要改进算法，而且用户也感受不到算法好坏对程序的影响，可事实真是这样吗，即使CPU短时间内提高了100倍，但是我们一个O(n)的算法写出了O(n*n)的程序，当n=100的时候，那就相差100倍了，不要说更加复杂的算法了。
文章结束语摘录自：大话数据结构，其实文章的内容也是根据大话数据结构写出来的，有空的同学也可以读以下这本书，感觉书写的还是挺通俗易懂的
网友评论