一粉怕、算法

1.1 算法

算法是獨立存在的一種解決問題的方法和思想
算法可以用不同的語言進(jìn)行描述實現(xiàn)

eg:

C++描述、Python描述

1.1.1 算法的五大特性

具有算法的五大特性的思路就可以稱為算法

1.2 算法的時間效率

eg(算法的時間效率的引入):

a+b+c = 1000
a**2+b**2 = c**2

求出a,b,c可能的組合

• 單靠運行的時間來比較算法的優(yōu)劣并不一定是客觀準(zhǔn)確的
  運行時間 = 基本運算總數(shù)*基本運算的單位時間= 時間單位*單位時間

提示：

• 時間單位對應(yīng)基本操作數(shù)
• 基本單位的運行時間即單位時間離不開計算機(jī)環(huán)境（軟件系統(tǒng)和硬件系統(tǒng)）

• 評價算法時需要忽略機(jī)器的環(huán)境而客觀反映算法的時間效率即只考慮時間單位
• 考慮到實際價值耍共，時間單位只看量級，不看常量因子
  示例：基于數(shù)學(xué)的函數(shù)曲線熬甫，第一象限中不管常量因子如何奥邮，n^3始終大于n^2

1.3 算法的復(fù)雜度

算法的時間復(fù)雜度 T(n)和空間復(fù)雜度 S(n)統(tǒng)稱為算法的復(fù)雜度

1.3.1 時間復(fù)雜度

T(n)，n稱為問題規(guī)模

• T(n) = a * n^m 近似于 O(n^m)（大O記法）
  所以以后提到時間復(fù)雜度罗珍，都是T(n)中最特征的部分O(n^m)洽腺，而不是整個T(n)

• 因此我們最關(guān)注的是算法的最壞情況，即最壞時間復(fù)雜度噪沙，是算法的保證

1. 時間復(fù)雜度的基本計算規(guī)則

• 判斷一個算法的效率時辐马，往往只看操作數(shù)量的最高次項，其他次要項和常數(shù)項可以忽略
• 沒有特殊說明局义，算法的時間復(fù)雜度就是最壞時間復(fù)雜度

2. 常見的時間復(fù)雜度

執(zhí)行次數(shù)函數(shù)示例	階	非正式語
	O()	常數(shù)階
	O()	對數(shù)階
	O()	線性階
	O()	階
	O()	平方階
	O()	立方階
	O()	指數(shù)階
	O()	階乘階
	O()	?

• 從上往下喜爷，時間復(fù)雜度越來越大

提示：

• 簡寫為

3. Python內(nèi)置類型性能分析

(1) timeit模塊

用來測試一小段python代碼的執(zhí)行速度

import timeit


timeit.Timer(stmt='pass', setup='pass')
# timeit()會重新開辟空間運行冗疮，即使用時需要導(dǎo)入含被測函數(shù)的包
avg_res = timeit.Timer.timeit(number=1000000)

• 啟動文件
  當(dāng).py自啟動時术幔，其模塊名應(yīng)該是__main__
  當(dāng)其他.py調(diào)用某.py時，調(diào)用的模塊名應(yīng)該是該.py的文件名

(2) 應(yīng)用

eg：

列表：
內(nèi)置操作的時間復(fù)雜度

定義列表的方式：
my_list = []

1. my_list.append()和my_list.insert()
2. [] + []
3. [x for x in range(10000)]
4. list(range(10000))

import timeit


def test_001():
    my_list = []
    for i in range(10000):
        my_list.append(i)


def test_002():
    my_list = []
    for i in range(10000):
        my_list = my_list + [i]


def test_003():
    my_list = [x for x in range(10000)]


def test_004():
    my_list = list(range(10000))


def test_005():
    my_list = []
    for i in range(10000):
        my_list.insert(0,i)


timer1 = timeit.Timer('test_001()', setup='from __main__ import test_001')
timer2 = timeit.Timer('test_002()', setup='from __main__ import test_002')
timer3 = timeit.Timer('test_003()', setup='from __main__ import test_003')
timer4 = timeit.Timer('test_004()', setup='from __main__ import test_004')
timer5 = timeit.Timer('test_005()', setup='from __main__ import test_005')
res1 = timer1.timeit(number=100)
res2 = timer2.timeit(number=100)
res3 = timer3.timeit(number=100)
res4 = timer4.timeit(number=100)
res5 = timer5.timeit(number=100)

print("append()：%.4f" % res1)
print("[] + []：%.4f" % res2)
print("[x for]：%.4f" % res3)
print("list()：%.4f" % res4)
print("insert()：%.4f" % res5)

結(jié)果：

append()：0.1225
[] + []：23.1820
[x for]：0.0504
list()：0.0303
insert()：3.0051

[]+[]> insert() > append() > [x for] > list()

字典：
內(nèi)置操作的時間復(fù)雜度

1.3.2 空間復(fù)雜度

S(n)

• 定義為該算法消耗的存儲空間湃密，它是問題規(guī)模n的函數(shù)
• 是對一個算法在運行過程中臨時占用存儲空間大小的量度

二诅挑、數(shù)據(jù)結(jié)構(gòu)

2.1 數(shù)據(jù)結(jié)構(gòu)

• 不同的數(shù)據(jù)結(jié)構(gòu)癌蚁，數(shù)據(jù)存儲方式不同幻梯，就會造成算法的時間復(fù)雜度不同

三、算法與數(shù)據(jù)結(jié)構(gòu)的區(qū)別

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

3.1 抽象數(shù)據(jù)類型

ADT （Abstract Data Type）
指一個數(shù)學(xué)模型以及定義在數(shù)學(xué)模型上的一組操作
即把數(shù)學(xué)類型和數(shù)學(xué)類型上的運算捆綁在一起進(jìn)行封裝

更新中......