Num01-->看下面案例兩種算法比較
問(wèn)題：如果 a+b+c=1000，且 a2+b2=c^2（a,b,c 為自然數(shù)），
如何求出所有a、b、c可能的組合?
#第一種計(jì)算解法：
import time
start_time = time.time()
for a in range(1001):
for b in range(1001):
for c in range(1001):
if 1000 == a + b + c and a ** 2 + b ** 2 == c ** 2:
print("a,b,c", (a, b, c))
end_time = time.time()
cast_time = end_time - start_time
print("花費(fèi)時(shí)間：%d" % cast_time)
# 結(jié)果是：
# a,b,c (0, 500, 500)
# a,b,c (200, 375, 425)
# a,b,c (375, 200, 425)
# a,b,c (500, 0, 500)
# 花費(fèi)時(shí)間：178秒
# 本案例共計(jì)計(jì)算步數(shù)為：1000*1000*1000*2
# 采用問(wèn)題規(guī)模N來(lái)標(biāo)記： N * N * N *2 = 2 * N^3
# 采用時(shí)間復(fù)雜度T(N)標(biāo)記：T(N)=2 * N^3
# 最終用大O記法為：O(N^3)
#第二種計(jì)算解法
import time
start_time = time.time()
for a in range(1001):
for b in range(1001):
c = 1000 - a - b
if a ** 2 + b ** 2 == c ** 2:
print("a,b,c", (a, b, c))
end_time = time.time()
cast_time = end_time - start_time
print("花費(fèi)時(shí)間：%d" % cast_time)
# 結(jié)果是：
# a,b,c (0, 500, 500)
# a,b,c (200, 375, 425)
# a,b,c (375, 200, 425)
# a,b,c (500, 0, 500)
# 花費(fèi)時(shí)間：秒
# 本案例共計(jì)計(jì)算步數(shù)為：1000*1000*3
# 采用問(wèn)題規(guī)模N來(lái)標(biāo)記： N * N * 3 = 3 * N^2
# 采用時(shí)間復(fù)雜度T(N)標(biāo)記：T(N)=3 * N^2
# 最終用大O記法為：O(N^2)
Num02-->定義
我們假定計(jì)算機(jī)執(zhí)行算法每一個(gè)基本操作的時(shí)間是固定的一個(gè)時(shí)間單位，那么有多少個(gè)基本操作就代表會(huì)花費(fèi)多少時(shí)間單位。顯然對(duì)于不同的機(jī)器環(huán)境而言，確切的單位時(shí)間是不同的，但是對(duì)于算法進(jìn)行多少個(gè)基本操作（即花費(fèi)多少時(shí)間單位）在規(guī)模數(shù)量級(jí)上卻是相同的，由此可以忽略機(jī)器環(huán)境的影響而客觀的反應(yīng)算法的時(shí)間效率。
對(duì)于算法的時(shí)間效率，我們可以用“大O記法”來(lái)表示。
“大O記法”：對(duì)于單調(diào)的整數(shù)函數(shù)f，如果存在一個(gè)整數(shù)函數(shù)g和實(shí)常數(shù)c>0，使得對(duì)于充分大的n總有f(n)<=c*g(n)，就說(shuō)函數(shù)g是f的一個(gè)漸近函數(shù)（忽略常數(shù)），記為f(n)=O(g(n))。也就是說(shuō)，在趨向無(wú)窮的極限意義下，函數(shù)f的增長(zhǎng)速度受到函數(shù)g的約束，亦即函數(shù)f與函數(shù)g的特征相似。
時(shí)間復(fù)雜度：假設(shè)存在函數(shù)g，使得算法A處理規(guī)模為n的問(wèn)題示例，所用時(shí)間為T(n)=O(g(n))，則稱O(g(n))為算法A的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度，記為T(n)
Num03-->如何理解大O記法
對(duì)于算法進(jìn)行特別具體的細(xì)致分析雖然很好，但在實(shí)踐中的實(shí)際價(jià)值有限。對(duì)于算法的時(shí)間性質(zhì)和空間性質(zhì)，最重要的是其數(shù)量級(jí)和趨勢(shì)，這些是分析算法效率的主要部分。而計(jì)量算法基本操作數(shù)量的規(guī)模函數(shù)中那些常量因子可以忽略不計(jì)。例如，可以認(rèn)為3n^2和100n^2屬于同一個(gè)量級(jí)，如果兩個(gè)算法處理同樣規(guī)模實(shí)例的代價(jià)分別為這兩個(gè)函數(shù)，就認(rèn)為它們的效率“差不多”，都為n^2級(jí)。
Num04-->最壞時(shí)間復(fù)雜度
分析算法時(shí)，存在幾種可能的考慮：
算法完成工作最少需要多少基本操作，即最優(yōu)時(shí)間復(fù)雜度
算法完成工作最多需要多少基本操作，即最壞時(shí)間復(fù)雜度
算法完成工作平均需要多少基本操作，即平均時(shí)間復(fù)雜度
對(duì)于最優(yōu)時(shí)間復(fù)雜度，其價(jià)值不大，因?yàn)樗鼪]有提供什么有用信息，其反映的只是最樂觀最理想的情況，沒有參考價(jià)值。
對(duì)于最壞時(shí)間復(fù)雜度，提供了一種保證，表明算法在此種程度的基本操作中一定能完成工作。
對(duì)于平均時(shí)間復(fù)雜度，是對(duì)算法的一個(gè)全面評(píng)價(jià)，因此它完整全面的反映了這個(gè)算法的性質(zhì)。但另一方面，這種衡量并沒有保證，不是每個(gè)計(jì)算都能在這個(gè)基本操作內(nèi)完成。而且，對(duì)于平均情況的計(jì)算，也會(huì)因?yàn)閼?yīng)用算法的實(shí)例分布可能并不均勻而難以計(jì)算。
因此，我們主要關(guān)注算法的最壞情況，亦即最壞時(shí)間復(fù)雜度。
Num05-->時(shí)間復(fù)雜度的幾條基本計(jì)算規(guī)則
1、基本操作，即只有常數(shù)項(xiàng)，認(rèn)為其時(shí)間復(fù)雜度為O(1)
2、順序結(jié)構(gòu)，時(shí)間復(fù)雜度按加法進(jìn)行計(jì)算
3、循環(huán)結(jié)構(gòu)，時(shí)間復(fù)雜度按乘法進(jìn)行計(jì)算
4、分支結(jié)構(gòu)，時(shí)間復(fù)雜度取最大值
5、判斷一個(gè)算法的效率時(shí)，往往只需要關(guān)注操作數(shù)量的最高次項(xiàng)，其它次要項(xiàng)和常數(shù)項(xiàng)可以忽略
6、在沒有特殊說(shuō)明時(shí)，我們所分析的算法的時(shí)間復(fù)雜度都是指最壞時(shí)間復(fù)雜度
Num06-->空間復(fù)雜度
類似于時(shí)間復(fù)雜度的討論，一個(gè)算法的空間復(fù)雜度S(n)定義為該算法所耗費(fèi)的存儲(chǔ)空間，它也是問(wèn)題規(guī)模n的函數(shù)。
漸近空間復(fù)雜度也常常簡(jiǎn)稱為空間復(fù)雜度。
空間復(fù)雜度(SpaceComplexity)是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度。
算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱為算法的復(fù)雜度。
------------------------
Num07-->常見時(shí)間復(fù)雜度
這里寫圖片描述
Num08-->常見時(shí)間復(fù)雜度之間的關(guān)系
這里寫圖片描述
Num09-->Python內(nèi)置類型性能分析
timeit模塊
timeit模塊可以用來(lái)測(cè)試一小段Python代碼的執(zhí)行速度。
class timeit.Timer(stmt='pass', setup='pass', timer=<timer function>)
Timer是測(cè)量小段代碼執(zhí)行速度的類。
stmt參數(shù)是要測(cè)試的代碼語(yǔ)句（statment）；
setup參數(shù)是運(yùn)行代碼時(shí)需要的設(shè)置；
timer參數(shù)是一個(gè)定時(shí)器函數(shù)，與平臺(tái)有關(guān)。
timeit.Timer.timeit(number=1000000)
Timer類中測(cè)試語(yǔ)句執(zhí)行速度的對(duì)象方法。number參數(shù)是測(cè)試代碼時(shí)的測(cè)試次數(shù)，默認(rèn)為1000000次。方法返回執(zhí)行代碼的平均耗時(shí)，一個(gè)float類型的秒數(shù)。
使用案例說(shuō)明timeit模塊的作用
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Author : xiaoke
# python內(nèi)置類型性能分析模塊
import timeit
# 以下采用五種list列表生成的函數(shù)，分析列表效率
# 采用相加的方法，[]+[]
def t1():
list_test = []
for i in range(1001):
list_test = list_test + [i]
# 采用尾部添加
def t2():
list_test = []
for i in range(1001):
list_test.append(i)
# 采用插入指定的位置
def t3():
list_test = []
for i in range(1001):
list_test.insert(0, i)
# 采用列表生成式
def t4():
list_test = [x for x in range(1001)]
# 采用list（）函數(shù)
def t5():
list_test = list(range(1001))
# 構(gòu)造
timeit1 = timeit.Timer("t1()", "from __main__ import t1")
timeit2 = timeit.Timer("t2()", "from __main__ import t2")
timeit3 = timeit.Timer("t3()", "from __main__ import t3")
timeit4 = timeit.Timer("t4()", "from __main__ import t4")
timeit5 = timeit.Timer("t5()", "from __main__ import t5")
# 測(cè)試
print("[]+[]: %f" % timeit1.timeit(number=1000))
print("append: %f" % timeit2.timeit(number=1000))
print("insert_start: %f" % timeit3.timeit(number=1000))
print("列表生成式: %f" % timeit4.timeit(number=1000))
print("list(): %f" % timeit5.timeit(number=1000))
# 結(jié)果為：
# []+[]: 1.662782
# append: 0.118913
# insert_start: 0.430096
# 列表生成式: 0.039850
# list(): 0.028044
Num10-->Python中l(wèi)ist內(nèi)置操作的時(shí)間復(fù)雜度
這里寫圖片描述
Num11-->Python中dict內(nèi)置操作的時(shí)間復(fù)雜度
這里寫圖片描述
