數據結構和算法對於python而言是他的靈魂;程序是數據結構加上算法來實現的,對於任何一門程式語言都離不開數據結構和算法,但是對於python而言內置了基礎的數據結構如列表、字典、集合等,再加上眾多包,所以弱化了數據結構和算法的使用。
但是在一些特定領域對數據結構和算法的要求也很高,如大數據分析和人工智慧之中應用廣泛;同時數據結構和算法關係程序運行的效率,是每個程式設計師不得不考慮的問題。
本月專題是python數據結構和算法;數據結構將涉及順序表、鍊表、堆棧、隊列、樹、二叉樹、平衡二叉樹、紅黑樹;算法將涉及排序算法(冒泡排序、選擇排序、插入排序、快速排序、希爾排序、歸併排序)、查找算法(順序查找、二分法查找、二叉樹查找、哈希查找)。
對於算法性能的衡量問題
算法性能的衡量不再是以運行開始到運行結束的時間來衡量,因為對於不同性能的計算機會產生不同的差異,所以算法的衡量主要以時間複雜度(以一種趨勢和運算數量級來表示)。
時間複雜度:假設存在函數g,使得算法A處理規模為n的問題示例所用時間為T(n)=O(g(n)),則稱O(g(n))為算法A的漸近時間複雜度,簡稱時間複雜度,記為T(n),它主要以算法的趨勢和數量級來看,如100*n的平方與1000*n的平方,他們的時間複雜度是相同的。
就像迭代輸出一個n*n的多維數組,他的時間複雜度就是N*N即n的平方
python內置數據結構(列表、字典)的操作時間複雜度如下:
針對列表而言,append時間複雜度優於insert,pop()優於pop(i)那是因為數據結構導致了操作前面位置的元素要挪動該元素之後的元素,所以算法對我們的性能性能提升關鍵。