廢話時(shí)間：

算法實(shí)際上是高于語(yǔ)言的。

所以我是第一?。?！

比如說(shuō)你的列表.sort 它里面其實(shí)就是實(shí)現(xiàn)了一種算法。

算法：一個(gè)計(jì)算過(guò)程，解決問(wèn)題的方法。

程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法。

一：時(shí)間復(fù)雜度：用來(lái)評(píng)估算法運(yùn)行效率（時(shí)間）的一個(gè)式子。

光年是距離。

一般來(lái)說(shuō)：時(shí)間復(fù)雜度高的算法比復(fù)雜度低的算法慢。

? 問(wèn)題規(guī)?；旧喜畈欢嘁粯拥臅r(shí)候。即n

? 與機(jī)器有關(guān)。

? 時(shí)間復(fù)雜度是獨(dú)立于機(jī)器的。

常見的時(shí)間復(fù)雜度：

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

如何簡(jiǎn)單判斷時(shí)間復(fù)雜度？

最好是根據(jù)運(yùn)行過(guò)程來(lái)估計(jì)

找到代表問(wèn)題規(guī)模的n  魑魅魍魎chi‘mei’wang‘liang

如何一眼判斷時(shí)間復(fù)雜度？

是否有循環(huán)減半的過(guò)程 -> o(logn)

幾層循環(huán)就是n的幾次方的復(fù)雜度

二：空間復(fù)雜度

用來(lái)評(píng)估算法內(nèi)存占用大小的一個(gè)式子

• 空間換時(shí)間

  
  例如：如果你想讓你的算法快點(diǎn)，就需要更多的緩存。
  
  

三：基本算法

算法里面重要的思想

遞歸的兩個(gè)特點(diǎn)：

- 調(diào)用自身

- 結(jié)束條件

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 漢諾塔

當(dāng)n個(gè)盤子時(shí)，把n-1看做一部分。

1. 把n-1個(gè)圓盤從a經(jīng)過(guò)c移動(dòng)到b

    2. 把第n個(gè)圓盤從a移動(dòng)到c

    3. 把n-1個(gè)圓盤從b經(jīng)過(guò)a移動(dòng)到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('本次總共運(yùn)行 %s 次'%t)

漢諾塔移動(dòng)次數(shù)的遞推式：h(x) = 2h(x-1)+1

前部分算法分為兩部分：查找和排序

3.1 列表查找：從列表中查找指定元素

- 輸入：列表、待查找元素

- 輸出：元素下標(biāo)或未查找到元素

3.2 順序查找

- 從列表第一個(gè)元素開始，順序進(jìn)行搜索，直到找到為止。

3.3 二分查找

- 從有序列表的候選區(qū)data[0:n]開始，通過(guò)對(duì)待查找的值和候選區(qū)中間值的比較，可以使候選區(qū)減少一半。

3.1 二分查找

• 使用二分查找來(lái)找3

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

  • Low high

    • ? mid

  • 如果high < low ，說(shuō)明你要找的值不存在。

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)

# 上面這個(gè)方法有問(wèn)題，不信你試。

# 遞歸版本二分查找

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

列表排序

- 列表排序

  - 將無(wú)序列表變?yōu)橛行蛄斜怼?.sort

- 應(yīng)用場(chǎng)景

  - 各種榜單

  - 各種表格

  - 給二分查找用

  - 給其他算法用

輸入：無(wú)序列表

輸出：有序列表

排序Low B三人組

- 冒泡排序

- 插入排序

- 選擇排序

算法關(guān)鍵點(diǎn)：

- 有序區(qū)

- 無(wú)序區(qū)

升序與降序

排序兇兇組：

- 快排

  - 思路：

    - 取一個(gè)元素p（第一個(gè)元素），使元素p歸位；

    - 列表被p分成兩部分，左邊逗比p小，右邊逗比p大‘

    - 遞歸完成排序。  遞歸終止條件：列表剩一個(gè)元素。

  - 算法關(guān)鍵點(diǎn)：1. 歸位  2. 遞歸

- 堆排

- 歸并排序

沒(méi)什么人用的排序：

- 基數(shù)排序

- 希爾排序

- 桶排序

總覽：