python算法学习（1）

目录

Python算法概念：

       算法（alogroithm）：一个计算过程，解决问题的方法

时间复杂度：（强调大概的时间，而不是具体的）

空间复杂度：评估算法内存占用大小的

查找问题：

顺序查找：从第一个元素到最后一个元素：

二分法查找：

二分法与顺序查找的区别

Python算法概念：

       算法（alogroithm）：一个计算过程，解决问题的方法

                         程序=数据结构+算法

时间复杂度：（强调大概的时间，而不是具体的）

空间复杂度：评估算法内存占用大小的

空间复杂度的表示方式与时间复杂度完全一样：

1. 算法使用了几个变量，o（1）
2. 算法使用了长度为n的一维列表，o（n）
3. 算法使用了m行n列的二维列表，o(mn)

    “空间换时间”（算法宁可占用很大空间，也要减少时间）

查找问题：

查找：在一些数据元素中，通过一定的方法找出与给定关键词的数据元素的过程。

列表查找（线性表查找）：从列表中查找指定要素

   输入：列表，待查找要素

   输出：元素下标（未找到元素时一般返回None或者-1）

 内置列表查找函数：index（）

顺序查找：从第一个元素到最后一个元素：

#顺序查找函数
def linear_search(li,val):
    for ind,v in enumerate(li):
        if v==val:
            return ind
    else:
        return none

结果：

二分法查找：

#二分法
def binary_search(li, val):
    left = 0
    right = len(li) - 1
    while left <= right:   #候选区有值
        mid = (right + left)//2
        if li[mid] == val:
            print("找到了")
            return mid
        elif li[mid] > val:
            right  = mid-1
            print("在中间值的左侧，继续找")
        else:
            left = mid+1
            print("在中间值的右侧，继续找")
    else:
        return None

结果：

>>> binary_search("1234567889", "8")
在中间值的右侧，继续找
找到了
7
>>> binary_search("1234567889", "5")
找到了
4
>>> binary_search("1234567889", "9")
在中间值的右侧，继续找
在中间值的右侧，继续找
在中间值的右侧，继续找
找到了
9

注意：二分法查找默认元素是有序的。

二分法与顺序查找的区别

两者区别：
二分法查找：

1. 二分法查找比顺序查找速度快；
2. 二分法是根据左、右指针与中指针比大小，来决定中指针变为左指针还是右指针；
3. 二分法查找前，最好一次升序或降序；
顺序查找：

顺序查找比二分法查找慢，但反而细心，因为它是从第一开始比较知道查找到停止；
共性：
1. 查找前，必须知道将要查找的“值”；
2. 查找目的是该“值”在列表中所在的位置；
注：数据量越大，越能体现出二分法的快速性；相反数据量小的话，两者都可以使用。

总结：
二分法查找（别称：对分查找或折半查找），顺序查找的要求，必须知道要查找的数值，然后在相应的列表中查找其在该列表所在的位置（下标）。