【Python100天學習筆記】Day17 資料結構與算法

資料結構和算法

• 算法：解決問題的方法和步驟
• 評價算法的好壞：漸近時間複雜度和漸近空間複雜度。
• 漸近時間複雜度的大O标記：

  

  - 常量時間複雜度 - 布隆過濾器 / 哈希存儲

  

  - 對數時間複雜度 - 折半查找（二分查找）

  

  - 線性時間複雜度 - 順序查找 / 計數排序

  

  - 對數線性時間複雜度 - 進階排序算法（歸并排序、快速排序）

  

  - 平方時間複雜度 - 簡單排序算法（選擇排序、插入排序、冒泡排序）

  

  - 立方時間複雜度 - Floyd算法 / 矩陣乘法運算

  

  - 幾何級數時間複雜度 - 漢諾塔

  

  - 階乘時間複雜度 - 旅行經銷商問題 - NPC

"""
貪婪法：在對問題求解時，總是做出在目前看來是最好的選擇，不追求最優解，快速找到滿意解。
輸入：
20 6
電腦 200 20
收音機 20 4
鐘 175 10
花瓶 50 2
書 10 1
油畫 90 9
"""
class Thing(object):
    """物品"""

    def __init__(self, name, price, weight):
        self.name = name
        self.price = price
        self.weight = weight

    @property
    def value(self):
        """價格重量比"""
        return self.price / self.weight


def input_thing():
    """輸入物品資訊"""
    name_str, price_str, weight_str = input().split()
    return name_str, int(price_str), int(weight_str)


def main():
    """主函數"""
    max_weight, num_of_things = map(int, input().split())
    all_things = []
    for _ in range(num_of_things):
        all_things.append(Thing(*input_thing()))
    all_things.sort(key=lambda x: x.value, reverse=True)
    total_weight = 0
    total_price = 0
    for thing in all_things:
        if total_weight + thing.weight <= max_weight:
            print(f'小偷拿走了{thing.name}')
            total_weight += thing.weight
            total_price += thing.price
    print(f'總價值: {total_price}美元')


if __name__ == '__main__':
    main()           

複制

分治法例子：快速排序。

"""
快速排序 - 選擇樞軸對元素進行劃分，左邊都比樞軸小右邊都比樞軸大
"""
def quick_sort(items, comp=lambda x, y: x <= y):
    items = list(items)[:]
    _quick_sort(items, 0, len(items) - 1, comp)
    return items


def _quick_sort(items, start, end, comp):
    if start < end:
        pos = _partition(items, start, end, comp)
        _quick_sort(items, start, pos - 1, comp)
        _quick_sort(items, pos + 1, end, comp)


def _partition(items, start, end, comp):
    pivot = items[end]
    i = start - 1
    for j in range(start, end):
        if comp(items[j], pivot):
            i += 1
            items[i], items[j] = items[j], items[i]
    items[i + 1], items[end] = items[end], items[i + 1]
    return i + 1           

複制

回溯法例子：騎士巡邏。

"""
遞歸回溯法：叫稱為試探法，按選優條件向前搜尋，當搜尋到某一步，發現原先選擇并不優或達不到目标時，就退回一步重新選擇，比較經典的問題包括騎士巡邏、八皇後和迷宮尋路等。
"""
import sys
import time

SIZE = 5
total = 0


def print_board(board):
    for row in board:
        for col in row:
            print(str(col).center(4), end='')
        print()


def patrol(board, row, col, step=1):
    if row >= 0 and row < SIZE and \
        col >= 0 and col < SIZE and \
        board[row][col] == 0:
        board[row][col] = step
        if step == SIZE * SIZE:
            global total
            total += 1
            print(f'第{total}種走法: ')
            print_board(board)
        patrol(board, row - 2, col - 1, step + 1)
        patrol(board, row - 1, col - 2, step + 1)
        patrol(board, row + 1, col - 2, step + 1)
        patrol(board, row + 2, col - 1, step + 1)
        patrol(board, row + 2, col + 1, step + 1)
        patrol(board, row + 1, col + 2, step + 1)
        patrol(board, row - 1, col + 2, step + 1)
        patrol(board, row - 2, col + 1, step + 1)
        board[row][col] = 0


def main():
    board = [[0] * SIZE for _ in range(SIZE)]
    patrol(board, SIZE - 1, SIZE - 1)


if __name__ == '__main__':
    main()           

複制

動态規劃例子：子清單元素之和的最大值。

說明：子清單指的是清單中索引（下标）連續的元素構成的清單；清單中的元素是int類型，可能包含正整數、0、負整數；程式輸入清單中的元素，輸出子清單元素求和的最大值，例如：

輸入：1 -2 3 5 -3 2

輸出：8

輸入：0 -2 3 5 -1 2

輸出：9

輸入：-9 -2 -3 -5 -3

輸出：-2

def main():
    items = list(map(int, input().split()))
    overall = partial = items[0]
    for i in range(1, len(items)):
        partial = max(items[i], partial + items[i])
        overall = max(partial, overall)
    print(overall)


if __name__ == '__main__':
    main()           

複制

說明：這個題目最容易想到的解法是使用二重循環，但是代碼的時間性能将會變得非常的糟糕。使用動态規劃的思想，僅僅是多用了兩個變量，就将原來O(N^2) 複雜度的問題變成了O(N)。