算法の 前戏

作者: Ugfly | 来源:发表于2018-02-01 18:30 被阅读0次

废话时间:


算法实际上是高于语言的。

所以我是第一!!!

比如说你的列表.sort 它里面其实就是实现了一种算法。

算法:一个计算过程,解决问题的方法。

程序 = 数据结构 + 算法。

一:时间复杂度:用来评估算法运行效率(时间)的一个式子。


光年是距离。

一般来说:时间复杂度高的算法比复杂度低的算法慢。

​ 问题规模基本上差不多一样的时候。即n

​ 与机器有关。

​ 时间复杂度是独立于机器的。

常见的时间复杂度:


o(1) < o(logn) < o(n) < o(nlogn) < o(n的平方) < o(n平方logn) < o(n的三次方)

如何简单判断时间复杂度?


最好是根据运行过程来估计

找到代表问题规模的n  魑魅魍魉chi‘mei’wang‘liang

如何一眼判断时间复杂度?

是否有循环减半的过程 -> o(logn)

几层循环就是n的几次方的复杂度

二:空间复杂度


用来评估算法内存占用大小的一个式子

  • 空间换时间

    
    例如:如果你想让你的算法快点,就需要更多的缓存。
    
    

三:基本算法

算法里面重要的思想


递归的两个特点:

- 调用自身

- 结束条件

def qq(n):

    if n == 0 :

        print('我的小可爱',end='')

    else:

        print('抱着',end='')

        qq(n-1)

        print('的我',end='')

qq(5)

# 抱着抱着抱着抱着抱着我的小可爱的我的我的我的我的我

def fun(x):

    if x > 0:

        print(x)

        fun(x-1)

def func(x):

    if x > 0:

        func(x-1)

3.0 汉诺塔


当n个盘子时,把n-1看做一部分。

1. 把n-1个圆盘从a经过c移动到b

    2. 把第n个圆盘从a移动到c

    3. 把n-1个圆盘从b经过a移动到c


t = 0

def hanoi(n,a,b,c):

    global t

    if n > 0:

        hanoi(n-1,a,c,b)

        t +=1

        print(':moving from %s --> %s.'%(a,c))

        hanoi(n-1,b,a,c)

hanoi(5,'a','b','c')

print('本次总共运行 %s 次'%t)


汉诺塔移动次数的递推式:h(x) = 2h(x-1)+1

前部分算法分为两部分:查找和排序


3.1 列表查找:从列表中查找指定元素

- 输入:列表、待查找元素

- 输出:元素下标或未查找到元素

3.2 顺序查找

- 从列表第一个元素开始,顺序进行搜索,直到找到为止。

3.3 二分查找

- 从有序列表的候选区data[0:n]开始,通过对待查找的值和候选区中间值的比较,可以使候选区减少一半。

3.1 二分查找

  • 使用二分查找来找3

    • 1,2,3,4,5,6,7,8,9

    • Low high

      • ​ mid
    • 如果high < low ,说明你要找的值不存在。


def erfen_search(li,val):

    low = 0

    high= len(li) - 1

    while low<=high:

        mid = (low+high) // 2

        if li[mid] == val:

            return  mid

        elif li[mid] < val:

            low = mid + 1

        else:

            high = mid - 1

a = erfen_search([1,2,3,4.123,123,12,3,12,3,12,3,21,3,213,21,321,3,213,21,321,3,21,4,3,543,53,45,435,342,5],435)

# 上面这个方法有问题,不信你试。

# 递归版本二分查找

def bin_search_rec(data_set,value,low,high):

    if low <= high:

        mid = (low + high) // 2

        if data_set[mid] == value:

            return mid

        elif data_set[mid] < value:

            low = mid + 1

            return bin_search_rec(data_set,value,low,high)

        else:

            high = mid - 1

            return bin_search_rec(data_set,value,low,high)

    else:

        return

列表排序


- 列表排序

  - 将无序列表变为有序列表。 .sort

- 应用场景

  - 各种榜单

  - 各种表格

  - 给二分查找用

  - 给其他算法用

输入:无序列表

输出:有序列表

排序Low B三人组

- 冒泡排序

- 插入排序

- 选择排序

算法关键点:

- 有序区

- 无序区

升序与降序

排序凶凶组:

- 快排

  - 思路:

    - 取一个元素p(第一个元素),使元素p归位;

    - 列表被p分成两部分,左边逗比p小,右边逗比p大‘

    - 递归完成排序。  递归终止条件:列表剩一个元素。

  - 算法关键点:1. 归位  2. 递归

- 堆排

- 归并排序

没什么人用的排序:

- 基数排序

- 希尔排序

- 桶排序

总览:

执行次数函数 非正式术语
12 O(1) 常数阶
2n+3 O(n) 线性阶
3n²+2n+1 O(n²) 平方阶
5log2n + 20 O(logn) 对数阶
2n + 3nlog2n + 19 O(nlogn) nlogn阶
6n³ + 2n² + 3n +4 O(n³) 立方阶
2" O(2") 指数阶

相关文章

  • 算法の 前戏

    废话时间: 一:时间复杂度:用来评估算法运行效率(时间)的一个式子。 一般来说:时间复杂度高的算法比复杂度低的算法...

  • 谜一样の算法

    谜一样の算法

  • 前戏

    我还记得初次在地铁口那里见你的时候,有点惶恐,你或许有点失望? 当时我就抱着一种能认识一个朋友也挺好,说不定还可以...

  • 前戏

    刚刚看到新闻里说,阿里巴巴战略投资欧尚和大润发以进一步发展马云的新零售经济。CEO张勇在发表会上还强调:未来所有的...

  • 前戏

    三天前,有人通知我要结婚了。 两天前,有熟人通知我要结婚了。 一天前,我最好的朋友通知我我要结婚了。 那么,是哪个...

  • 前戏

    男人说,我没钱。 女人说,你没戏。 干是两人没有前戏。

  • 前戏

    究竟在坚持什么 那个依然的故我? 还是在焦虑什么 这样跌撞地走着…… 犹豫,是一座座山 还是,那一条条宽阔的河 我...

  • 卡尔曼滤波剪影__Kalman Filtering · Make

    铺垫用の引论 Kalman Filtering 算法是一种最优滤波估计算法,有了它之后,就算只知道观测对象的少量不...

  • 用JavaScript实现常见的排序算法

    前戏 复习了一些比较常见的排序算法,用JS实现,带一些实现思路。 无图,无脑贴代码。。 比较排序 冒泡排序 比较相...

  • 21天,撩总裁!(10)

    本回篇:性爱的重头戏,前戏 01、 世面上之所以频频出现被强奸的现象,核心原因大抵都是因为: 没有前戏! 没有前戏...

网友评论

    本文标题:算法の 前戏

    本文链接:https://www.haomeiwen.com/subject/jjcjzxtx.html