算法基礎(chǔ)

算法

算法(Algorithm)：一個計算過程，解決問題的方法

DNiklaus Wirth:“程序=數(shù)據(jù)結(jié)構(gòu)+算法”

時間復(fù)雜度

時間復(fù)雜度：用來評估算法運(yùn)行效率的一個式子

?

?

時間復(fù)雜度-小結(jié)

時間復(fù)雜度是用來估計算法運(yùn)行時間的一個式子(單位)。
一般來說，時間復(fù)雜度高的算法比復(fù)雜度低的算法慢。
常見的時間復(fù)雜度(按效率排序)

O(1)< O(logn)< O(n)< O(nlogn)< O(n²)< O(n²logn)< O(n³)
復(fù)雜問題的時間復(fù)雜度
O(n！)O(2ⁿ)O(nⁿ)..

如何簡單快速地判斷算法復(fù)雜度

快速判斷算法復(fù)雜度(適用于絕大多數(shù)簡單情況)：
　　確定問題規(guī)模n
　　循環(huán)減半過程→logn
　　k層關(guān)于n的循環(huán)→n^k
復(fù)雜情況：根據(jù)算法執(zhí)行過程判斷

空間復(fù)雜度

空間復(fù)雜度：用來評估算法內(nèi)存占用大小的式子
空間復(fù)雜度的表示方式與時間復(fù)雜度完全一樣
　　算法使用了幾個變量：O(1)
　　算法使用了長度為n的一維列表：O(n)
　　算法使用了m行n列的二維列表：O(mn)
“空間換時間”

遞歸的兩個特點(diǎn)：
　　調(diào)用自身
　　結(jié)束條件

?

?遞歸實例：漢諾塔問題

大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序擺著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。
在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
64根柱子移動完畢之日，就是世界毀滅之時。

?

漢諾塔移動次數(shù)的遞推式：h(x)=2h(x-1)+1
h(64)=18446744073709551615
假設(shè)婆羅門每秒鐘搬一個盤子，則總共需要5800億年！

def hanoi(n, a, b, c):if n > 0: # 盤子大于0才執(zhí)行hanoi(n - 1, a, c, b) # 將n-1個盤 從a經(jīng)過c移動到 bprint("moving pan from %s to %s" % (a, c)) # 將第n個盤移動到chanoi(n - 1, b, a, c) # 將n-1 個盤 從b 經(jīng)過a 移動到chanoi(3, 'A', 'B', 'C')# 將n-1個盤(除了底層的第n個盤)看成一個整體，""" move pan from A to C move pan from A to B move pan from C to B move pan from A to C move pan from B to A move pan from B to C move pan from A to C """ View Code

列表查找

查找
查找：在一些數(shù)據(jù)元素中，通過一定的方法找出與給定關(guān)鍵字相同的數(shù)據(jù)元素的過程。
列表查找(線性表查找)：從列表中查找指定元素

輸入：列表、待查找元素
輸出：元素下標(biāo)(未找到元素時一般返回None或-1)

內(nèi)置列表查找函數(shù)：index()

順序查找(Linear Search)

順序查找：也叫線性查找，從列表第一個元素開始，順序進(jìn)行搜索，直到找到元素或搜索到列表最后一個元素為止。
時間復(fù)雜度：O(n)

?

二分查找(Binary Searh)

二分查找：又叫折半查找，從有序列表的初始候選區(qū)li[0：n]開始，通過對待查找的值與候選區(qū)中間值的比較，可以使候選區(qū)減少一半。

def binary(data_list, value):low = 0high = len(data_list) - 1while low <= high:mid = (low + high) // 2 # 折半if data_list[mid] == value:return midelif data_list[mid] > value:high = mid - 1else:low = mid + 1data_list = [1, 2, 3, 4, 5, 6, 7, 8, 9] value = 5 index = binary(data_list, value) print("index in data_list:%s ,search value test:%s "%(index,data_list[index]))""" index in data_list:4 ,search value test:5 """

總結(jié)

以上是生活随笔為你收集整理的sf-1 算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。