Fork me on GitHub

《算法图解》笔记

《算法图解》这本书的读书笔记,后来发现没什么可记的。

In [ ]:
print "python2"

6.18促销买书时候为了凑单,就顺便买了本算法图解(39元)。这本书早已声明远播,《算法图解》的确是一本非常优秀的入门书,可惜不适合我了。花了一天时间看完了,写的非常生动有趣。

我觉得目标读者是:

  • 计算机专业的大一学生
  • 对算法感兴趣的计算机爱好者

看这本书一点都不会觉得累,真的像看小说一样。:)

选择排序

时间复杂度$O(n^2)$

In [2]:
def findSamllest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1,len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index
    
def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSamllest(arr)
        newArr.append(arr.pop(smallest))
    return newArr

print selectionSort([5,3,6,2,10])
    
[2, 3, 5, 6, 10]

快速排序

使用递归实现。其时间复杂度和每次选作基准值的元素有关。最好每次随机选择。

时间复杂度:

  • 平均$O(nlog(n))$
  • 最糟糕$O(n^2)$
In [4]:
def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]   
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10,5,2,3])
[2, 3, 5, 10]

迪科特斯拉算法

在单向加权图中寻找最短路径,仅当权重为正数时此算法才有效。
若图中包含负权边,请使用贝尔曼-福德算法。

In [1]:
# 用散列表储存图
graph = {}

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph["a"] = {}
graph["a"]["fin"] = 1

graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5

graph["fin"] = {}  # 终点无数据
# 储存开销表
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
# 储存父节点表
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
# 记录处理过的节点
processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

# 算法开始
node = find_lowest_cost_node(costs)
while node is not None:
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost:
            costs[n] = new_cost
            parents[n] = node
    processed.append(node)
    node = find_lowest_cost_node(costs)

print costs,parents,processed
{'a': 5, 'b': 2, 'fin': 6} {'a': 'b', 'b': 'start', 'fin': 'a'} ['b', 'a', 'fin']

贪婪算法

对于NP问题,每次获取局部最优解,最终获取近似解。

In [1]:
# 找出广播台的最小集合,使得广播节目可以覆盖美国的所有州。
# 所有的州
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])
# 可供选择的广播台清单
stations = {}
stations["kone"] = set(['id', 'nv', 'ut'])
stations['ktwo'] = set(['wa', 'id', 'mt'])
stations['kthree'] = set(['or', 'nv', 'ca'])
stations['kfour'] = set(['nv', 'ut'])
stations['kfive'] = set(['ca', 'az'])
# 存储最终选择的广播台
final_stations = set()

while states_needed:
    best_station = None
    states_covered = set()
    for station, states_for_station in stations.items():
        covered = states_needed & states_for_station
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered
    final_stations.add(best_station)
    states_needed -= states_covered

print(final_stations)
set(['ktwo', 'kthree', 'kone', 'kfive'])

Comments