算法復(fù)雜度
不再使用毫秒測量時(shí)間,而是以程序執(zhí)行的基本步數(shù)為單位進(jìn)行測量。而人們通常最關(guān)注最差情形。
通常對于規(guī)模特別大的輸入,我們才會擔(dān)心算法的效率。作為一種對“特別大”的表示方法,漸近表示法描述了輸入規(guī)模
趨近于無窮大時(shí)的算法復(fù)雜度。
漸進(jìn)復(fù)雜度
# 書中例子練習(xí)如下：
>>> def f(x):
... """假設(shè)x是正整數(shù)"""
... ans = 0
... #常數(shù)時(shí)間循環(huán)
... for i in range(1000):
... ans += 1
... print('Number of additions so far', ans)
... #x時(shí)間循環(huán)
... for i in range(x):
... ans += 1
... print('Number of additions so far', ans)
... #x**2時(shí)間的嵌套循環(huán)
... for i in range(x):
... for j in range(x):
... ans += 1
... ans += 1
... print('Number of additions so far', ans)
... return ans
...
# 調(diào)用10次
>>> f(10)
Number of additions so far 1000
Number of additions so far 1010
Number of additions so far 1210
1210
#調(diào)用1000次數(shù)
>>> f(1000)
Number of additions so far 1000
Number of additions so far 2000
Number of additions so far 2002000
2002000
如果假設(shè)執(zhí)行每行代碼需要一個(gè)單位時(shí)間,那么這個(gè)函數(shù)的運(yùn)行時(shí)間可以描述為1000 + x +2x^2 。常數(shù)1000對應(yīng)著第一個(gè)循環(huán)執(zhí)行的次數(shù)。x項(xiàng)對應(yīng)著第二個(gè)循環(huán)執(zhí)行的次數(shù)。
通過上面的分析,我們可以使用以下規(guī)則描述算法的漸近復(fù)雜度:
1、如果運(yùn)行時(shí)間是一個(gè)多項(xiàng)式的和,那么保留增長速度最快的項(xiàng),去掉其他各項(xiàng);
2、如果剩下的項(xiàng)是個(gè)乘積,那么去掉所有常數(shù)。
1、常數(shù)復(fù)雜度
2、對數(shù)復(fù)雜度
>>> def intToStr(i):
... """假設(shè)i是非負(fù)整數(shù)，返回一個(gè)表示i的十進(jìn)制字符串"""
... digits = '0123456789'
... if i == 0:
... return '0'
... result = ''
... while i > 0:
... result = digits[i%10] + result
... i = i//10
... return result
...
>>> intToStr(10)
'10'
# intToStr 的復(fù)雜度是O(log(i))。
3、線性復(fù)雜度
>>> def addDigits(s):
... """假設(shè)s是字符串，其中每個(gè)字符都是十進(jìn)制數(shù)。decimal digit. 返回s中所有數(shù)值之和"""
... val = 0
... for c in s:
... val += int(c)
... return val
...
>>> addDigits('12345')
15
# 我們?nèi)匀患僭O(shè)表示數(shù)字的字符在常數(shù)時(shí)間內(nèi)被轉(zhuǎn)換為整數(shù),那么這個(gè)函數(shù)的復(fù)雜度就與s的長度成線性關(guān)系,也就是O(len(s))。
4、對數(shù)線性復(fù)雜度
5、多項(xiàng)式復(fù)雜度
>>> def isSubset(L1, L2):
... """假設(shè)L1和L2是列表。
... 如果L1中的每個(gè)元素也在L2中出現(xiàn),則返回True
... 否則返回False。"""
... for e1 in L1:
... matched = False
... for e2 in L2:
... if e1 == e2:
... matched = True
... break
... if not matched:
... return False
... return True
...
>>> isSubset([1,2,3],[3])
False
>>> isSubset([1,2,3],[3,2,1,6,9])
True
>>>
"""
程序每次執(zhí)行到內(nèi)層循環(huán)時(shí),內(nèi)層循環(huán)都要執(zhí)行O(len(L2))次。函數(shù) isSubset 要執(zhí)行外部循
環(huán)O(len(L1))次,所以執(zhí)行到內(nèi)層循環(huán)的次數(shù)也是O(len(L1))。因此,函數(shù) isSubset 的復(fù)雜度是
O(len(L1))*O(len(L2))。
"""
6、指數(shù)復(fù)雜度
>>> def getBinaryRep(n, numDigits):
... """
... 假設(shè)n和numDigits為非負(fù)整數(shù)
... 返回一個(gè)長度為numDigits的字符串,為n的二進(jìn)制表示
... """
... result = ''
... while n > 0:
... result = str(n%2) + result
... n = n//2
... if len(result) > numDigits:
... raise ValueError('not enough digits')
... for i in range(numDigits - len(result)):
... result = '0' + result
... return result
...
>>> def genPowerset(L):
... """
... 假設(shè)L是列表
... 返回一個(gè)列表,包含L中元素所有可能的集合。例如,如果L=[1, 2],則返回的列表包含元素[1]、[2]和[1,2]
... """
... powerset = []
... for i in range(0, 2**len(L)):
... binStr = getBinaryRep(i, len(L))
... subset = []
... for j in range(len(L)):
... if binStr[j] == '1':
... subset.append(L[j])
... powerset.append(subset)
... return powerset
...
>>> genPowerset(['x','y',1])
[[], [1], ['y'], ['y', 1], ['x'], ['x', 1], ['x', 'y'], ['x', 'y', 1]]
"""
函數(shù) genPowerset(L) 具有指數(shù)復(fù)雜度，函數(shù)中調(diào)用getBinaryRep()函數(shù)。
返回一個(gè)列表的列表,包含 L 中元素所有可能的組合。
例如,如果 L 是['x', 'y'] ,那么 L 的冪集就是包含 [ ] 、 ['x'] 、 ['y'] 和 ['x', 'y'] 這些列表的列表。
"""
一些簡單算法和數(shù)據(jù)結(jié)構(gòu)
下面列出了一些最常用的大O表示法實(shí)例。 n表示函數(shù)的輸入規(guī)模。
1、O(1)表示常數(shù)運(yùn)行時(shí)間。
2、 O(logn)表示對數(shù)運(yùn)行時(shí)間。
3、O(n)表示線性運(yùn)行時(shí)間。
4、 O(nlogn)表示對數(shù)線性運(yùn)行時(shí)間。
5、 O(nk)表示多項(xiàng)式運(yùn)行時(shí)間，注意k是常數(shù)。
6、 O(cn)表示指數(shù)運(yùn)行時(shí)間，這時(shí)常數(shù)c為底數(shù)，復(fù)雜度為c的n次方。
簡單算法及數(shù)據(jù)結(jié)構(gòu)
1、歸并排序
# 書中的這個(gè)例子，自己練習(xí)完后發(fā)現(xiàn)無輸出，應(yīng)該是哪里出現(xiàn)問題了。
>>> def merge(left, right, compare):
... """
... 假設(shè)left和right是兩個(gè)有序列表,compare定義了一種元素排序規(guī)則。
... 返回一個(gè)新的有序列表(按照compare定義的順序),其中包含與
... (left+right)相同的元素。"""
... result = []
... i,j = 0, 0
... while i < len(left) and j < len(right):
... if compare(left[i], right[j]):
... result.append(left[i])
... i += 1
... else:
... result.append(right[j])
... j += 1
... while (i < len(left)):
... result.append(left[i])
... i += 1
... while (j < len(right)):
... result.append(right[j])
... j += 1
... return result
...
>>> def mergeSort(L, compare = lambda x, y: x < y):
... """
... 假設(shè)L是列表,compare定義了L中元素的排序規(guī)則
... on elements of L
... 返回一個(gè)新的具有L中相同元素的有序列表。"""
... if len(L) < 2:
... return L[:]
... else:
... middle = len(L)//2
... left = mergeSort(L[:middle], compare)
... right = mergeSort(L[middle:], compare)
... return merge(left, right, compare)
2、將函數(shù)用作參數(shù)
>>> def lastNameFirstName(name1, name2):
... arg1 = name1.split(' ')
... arg2 = name2.split(' ')
... if arg1[1] != arg2[1]:
... return arg1[1] < arg2[1]
... else: #姓相同,則按照名排序
... return arg1[0] < arg2[0]
...
>>> def firstNameLastName(name1, name2):
... arg1 = name1.split(' ')
... arg2 = name2.split(' ')
... if arg1[0] != arg2[0]:
... return arg1[0] < arg2[0]
... else: #名相同,則按照姓排序
... return arg1[1] < arg2[1]
...
>>> L = ['Tom Brady', 'Eric Grimson', 'Gisele Bundchen']
>>> newL = mergeSort(L, lastNameFirstName)
print('Sorted by last name =', newL)
# 也是按照書中的例子輸入完之后，并沒有輸出。也應(yīng)該是哪里有問題，可能是版本問題。
3、python中的排序
>>> L = [3,5,2]
>>> L
[3, 5, 2]
>>> sorted(L)
[2, 3, 5]
>>> D = {'a':12,'c':5,'b':'dog'}
>>> L.sort()
>>> print(L)
[2, 3, 5]
>>> L
[2, 3, 5]
>>> sorted(D)
['a', 'b', 'c']
>>> D.sort()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'dict' object has no attribute 'sort'
視頻中的一些練習(xí)
對列表進(jìn)行升序排序
In [27]: def swapSort(L):
...: """ L is a list on integers """
...: print ("Original L: ", L)
...: for i in range(len(L)):
...: for j in range(i+1, len(L)):
...: if L[j] < L[i]:
...: # the next line is a short
...: # form for swap L[i] and L[j]
...: L[j], L[i] = L[i], L[j]
...: print (L)
...: print ("Final L: ", L)
...:
In [28]: L = [3,4,1,2,9,8]
In [30]: swapSort(L)
Original L: [3, 4, 1, 2, 9, 8]
[1, 4, 3, 2, 9, 8]
[1, 3, 4, 2, 9, 8]
[1, 2, 4, 3, 9, 8]
[1, 2, 3, 4, 9, 8]
[1, 2, 3, 4, 8, 9]
Final L: [1, 2, 3, 4, 8, 9]
變?yōu)榻敌蚺判?/h6>
注意與上面進(jìn)行區(qū)分，以及復(fù)雜度之間的變化
In [31]: def modSort(L):
...: """ L is a list on integers """
...: print ("Original L: ", L)
...: for i in range(len(L)):
...: for j in range(len(L)): #與上面的代碼相比，這里進(jìn)行一下變更，
...: if L[j] < L[i]:
...: # the next line is a short
...: # form for swap L[i] and L[j]
...: L[j], L[i] = L[i], L[j]
...: print (L)
...: print ("Final L: ", L)
...:
In [32]: modSort(L)
Original L: [1, 2, 3, 4, 8, 9]
[2, 1, 3, 4, 8, 9]
[3, 1, 2, 4, 8, 9]
[3, 2, 1, 4, 8, 9]
[4, 2, 1, 3, 8, 9]
[4, 3, 1, 2, 8, 9]
[4, 3, 2, 1, 8, 9]
[8, 3, 2, 1, 4, 9]
[8, 4, 2, 1, 3, 9]
[8, 4, 3, 1, 2, 9]
[8, 4, 3, 2, 1, 9]
[9, 4, 3, 2, 1, 8]
[9, 8, 3, 2, 1, 4]
[9, 8, 4, 2, 1, 3]
[9, 8, 4, 3, 1, 2]
[9, 8, 4, 3, 2, 1]
Final L: [9, 8, 4, 3, 2, 1]
第10講 內(nèi)存和查找
L10 PROBLEM 4
In [16]: def search(L, e):
...: for i in range(len(L)):
...: if L[i] == e:
...: return True
...: if L[i] > e:
...: return False
...: return False
...:
In [17]: def search3(L, e):
...: if L[0] == e:
...: return True
...: elif L[0] > e:
...: return False
...: else:
...: return search3(L[1:], e)
答案給的是：
search and search3 return the same answers provided L is non-empty and e is in L
實(shí)際上下面這樣輸出結(jié)果也是一致的
In [18]: search([2,3,4,8],5)
Out[18]: False
In [19]: search3([2,3,4,8],5)
Out[19]: False
