算法入门

算法

发布日期: 2021-07-06

更新日期: 2021-07-07

文章字数: 546

阅读次数:

算法

一个计算过程，解决问题的方法

“程序=数据结构+算法”

时间复杂度-小结

时间复杂度用来估计算法运行时间的一个式子（单位）。
一般来说，时间复杂度高的算法比复杂度低的算法慢
常见的时间复杂度（按效率排序）
- O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^2logn)<O(n^3)
复杂问题的时间复杂度
- O(n!) O(2^n) O(n^n)

如何简单快速地判断算法复杂度

快速判断算法复杂度（适用绝大多数简单情况）：\
- 确定问题规模n
- 循环减半过程——logn
- k层关于n的循环——n^k
复杂情况：根据算法执行过程判断

空间复杂度

用来评估算法内存占用大小的式子
空间复杂度的表示方式与时间复杂度完全一样
- 算法使用几个变量：O(1)
- 算法使用了长度为n的一堆列表：O(n)
- 算法使用了m行n列的二维列表：O(mn)
”空间换时间“：宁可占用多的空间来提升时间

查找算法

顺序查找（线性查找）：从第一个元素往下找，直到找到或者搜索到列表最后一个元素为止

时间复杂度：O(n)

def linear_search(data_set,value):
    '''

    :param data_set: 列表
    :param value: 要查的数据
    :return:循环找到需要的数据，返回下标
    '''
    for ind,v in enumerate(data_set):
        if v == value:
            return ind
    else:
        return None

二分查找
时间复杂度：O(logn)
- 比O(n)也就是线性查找快得多

#二分查找
def binary_search(li,val):
    '''

    :param li: 列表
    :param val: 需要查找的数
    :return:
    '''
    left = 0
    right = len(li) -1

    while left<=right:  # 候选区有值
        mid = (left+right) //2  # 找到候选区中间值
        if li[mid] == val:  # 如果直接找到要找的值，返回
            return mid
        elif li[mid] >val:  # 查找值在mid左侧
            right = mid-1
        else:  # li[mid]<val 带查找的值在mid右侧
            left = mid+1
    else:
        return None