算法的意义在于让代码可行、高效、低占用资源。明白代码底层逻辑，方便使用和阅读代码。

算法就是任何明确定义的计算过程，它接收一些值或集合作为输入，并产生一些值或集合作为输出。这样，算法就是将输入转换为输出的一系列计算过程。

·有穷性：如果你设计的算法永无休止地尝试解决问题，那么它是无用的。
·确定性：算法的每一步都必须准确定义，在任何场景下指令都应当没有歧义。
·可行性：一个算法被设计用以解决某个问题，那么它就应当能解决这个
问题，并且仅仅使用纸和笔就能证明该算法是收敛的。

1.计算运行时间

import time

start_time = time.time()

a=1
b=2
print(a+b)

end_time = time.time()
print("程序已完成,总计用时:%f" % (end_time-start_time))

2.大O表示法与时间复杂度

称一个函数f(n)是O(g(n))，当且仅当存在常数c>0和n0>=1，对一切n>n0均有0<=|f(n)|<=c|g(n)|成立，也称函数f(n)以g(n)为界或者称f(n)囿于g(n)。记作f(n)=O(g(n))。我们使用O记号来给出函数的一个在常量因子内的上界。

新定义：我们将算法执行运算的操作数丢弃掉低阶项，再去掉所有的系数，就是算法的时间复杂度。

在它前面加一个O，就是大O表示法：O（n）,其中n为操作数

操作数                   时间复杂度                     名称
3                         O(1)                         常数
105logn+2                 O(logn)                      对数 
2n+4                      O(n)                         线性
7n+9nlogn+39              O(nlogn)                     nlogn
3n^2+2n+5                 O(n^2)                       平方
n^3+20000n^2              O(n^3)                       多项式
2^n                       O(2^n)                       指数

#所消耗的时间从小到大：
 O(1) < O(logn) <O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

3.算法分析法则及其他渐进符号

①一般法则
法则1：（循环结构，时间复杂度按乘法进行计算）
for循环：假设循环体时间复杂度为O(n)，循环次数为m，则时间复杂度为O(nm)
法则2：（循环结构，时间复杂度按乘法进行计算）
嵌套的for循环：O(nm*p)
法则3：（顺序结构，时间复杂度按加法进行计算）
顺序语句：第一个循环为O(n)，第二个循环为O(n^{2)，则求和（取较大值），即O(n}2)
法则4：（分支结构，时间复杂度取最大值）
if-else语句：类比法则3

②3个概念
最优、平均、最坏时间复杂度
算法完成工作最少需要多少基本操作，即最优时间复杂度 --- 其价值不大
算法完成工作最多需要多少基本操作，即最坏时间复杂度（**） --- 提供了一种保证，表名算法在此中程度的基本操作中一定能完成工作
算法完成工作平均需要多少基本操作，即平均时间复杂度

③其他渐进符号

大O一般表示最坏复杂度，是一个集合，当函数的大小只有上界，没有明确下界的时候，则可以使用大O表示法。f（n）= O（g（n））正式的数学定义：存在正常数c、n、n0，当n>n0的时，对于任意的f（n）对符合0<= f（n）<= c.g（n）。
大Ω表示最优复杂度， 当函数的大小只有下界，没有明确的上界的时候，可以使用大Ω表示法。f（n）= Ω（g（n））正式的数学定义：存在正常数c、n、n0，当n>n0的时，对于任意的f（n）对符合0<= c.g（n）<= f（n）。
大θ，当大O=大W时才会出现，f（n）= θ（c.g（n））正式的数学定义：存在正常数c1、c2、n、n0，当n>n0的时，对于任意的f（n）对符合c1.g（n）<= f（n）<= c2.g（n），c1.g（n）、c2.g（n）都是渐进正函数（当n趋于无穷大的时候，f（n）为正）
小o表示法，没有上界，大O表示法是存在一个常数c符合该条件，而小o表示法是对于所有的正常数c都符合该条件。
小ω表示法，没有下界

例题：
快速排序的平均时间复杂度和最坏时间复杂度是?
O(nlgn) , O(n^2)
平均复杂度相当于目标index在中间，类似二分法，最坏情况，每次从头到尾遍历整个数组

4.二分法查找（折半查找）

就是一种在有序数组中查找某一特定元素的搜素算法

先决条件：有序数组

主要思想是:(设查找的数组区间为array[low, high])
(1)确定该区间的中间位置K(2)将查找的值T与array[k]比较。若相等，查找成功返回此位置;否则确定新的查找区域，继续二分查找。

最坏/平均时间复杂度：O(logn)
最优时间/空间复杂度：O(1)

def binary_search(arr,key):
    start = 0
    end = len(arr) - 1
    while start <= end:
        mid=(start+end)//2
        if arr[mid]<key:
            start = mid + 1
        elif arr[mid] > key:
            end = mid - 1
        else:
            return mid
    return -1

alist = [12, 21, 24, 32, 39, 43, 67, 90]
print(binary_search(alist, 39))

5.数组和链表

在内存中，数组是一块连续的区域。
在使用前需要提前申请所占内存的大小，这样不知道需要多大的空间，就预先申请可能会浪费内存空间，即数组空间利用率低
插入数据时，待插入位置的的元素和它后面的所有元素都需要向后搬移
删除数据时，待删除位置后面的所有元素都需要向前搬移
因为数组的内存是连续的，想要访问那个元素，直接从数组的首地址处向后偏移就可以访问到了，类比网络电视可以选集播放

在内存中，链表元素的空间可以在任意地方，空间是分散的，不需要连续
链表中的元素都会两个属性，一个是元素的值，另一个是指针，此指针标记了下一个元素的地址
每一个数据都会保存下一个数据的内存的地址，通过此地址可以找到下一个数据
因为链表的空间是分散的，所以不具有随机访问性，如要需要访问某个位置的数据，需要从第一个数据开始找起，依次往后遍历，直到找到待查询的位置，故可能在查找某个元素时，时间复杂度达到O(N)，类比有限电视可以顺序播放
任意位置插入元素和删除元素效率较高，时间复杂度为O(1)

操作                        链表                       数组
查找                        O(n)                       O(1)
在头部插入/删除              O(1)                       O(n)
在尾部插入/删除              O(n)                       O(1)                
在中间插入/删除              O(n)                       O(n)

当插入删除很少，查询非常多，采用数组
当频繁的插入，遍历，查询检索很少，采用链表

6.顺序表和链表

线性表是最基本、最简单、也是最常用的一种数据结构。主要由顺序表示或链式表示，即包括顺序表和链表。在实际应用中，常以栈、队列、字符串等特殊形式使用。

数组的元素的位置称之为索引。通过索引可以引用数组，类比python中的应用

顺序表和链表的比较：

1. 顺序表可以顺序存取，也支持随机存取；链表只能顺序存取。
2. 顺序表逻辑上相邻的物理上也相邻；而链表不一定，它是用指针来描述元素之间的关系。
3. 顺序表插入和删除要移动大量元素；链表只需修改指针即可

7.栈和队列

栈是一端受限，一段允许进行操作的线性表。理解成一个装书的盒子。放书，取书，就是进行的操作。这个的特点就是，你放了一踏书，现在你想取书，你只能先把上面的书一个个取出来，即：先放的后取，后放的先取。放在栈上说，就是先进后出。
队列：是一种限定性的线性表。这样理解比较好，学生排队买饭。有什么特点呢？当然，你先来，就先打饭，先吃饭。抽象到队列上说，有队头，队尾，要想加入（入队），只能从队尾加，想走（出队），只能从队头走。即：先进先出。