算法學習筆記1----算法簡介

1.1算法是一組完成任務的指令，任何代碼片段都可視為代碼。

1.2二分查找：

在一個有序的元素清單（必須有序）。如果要查找的元素包含在清單中，則傳回其位置；否則傳回null。

工作原理：每次都從清單的中間進行查找，每次都排除一半的數字。

例：在1-100中找到一個我想的數。從50開始，小了，就找50-100之間的數75，大了，就找1-50之間的數25；以此類推，每次減少一半的數字，最終找到想要的數。

100-->50-->25-->13-->7-->4-->2-->1   7步

1.3簡單查找。就是傻找，一個一個的按着順序查找，不漏任何一個數。

簡單查找需要n步，而二分查找需要log2n步。

1.4Python代碼實作二分查找

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) / 2
        guess = list[mid]
        if guess == item:
            return mid
        elif guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

my_list = [1, 3, 5, 7, 9]

print(binary_search(my_list, 1))
print(binary_search(my_list, -1))
           

練習.（1）.假設有一個包含128個名字的有序清單，使用二分查找需要多少步？

                    log2128 = 7步

        (2).上面清單翻倍後最多需要幾步？

                log2256 = 8步

1.5運作時間。

設計程式，一般而言應選擇效率最高的算法，以最大限度的減少運作時間或占用空間。

簡單查找的查找次數和清單長度相同，這被稱為線性時間。

二分查找的運作時間為對數時間。

1.6.大O表示法

算法的運作時間以不同的速度增加。

大O表示法指出了算法有多快，即指出了算法運作時間的增速。簡單查找運作時間為O(n)。二分查找運作時間為O(log n)。

大O表示法指出了最糟情況下的運作時間。

一些常見的大O運作時間：

O(log n)，也叫對數時間，這樣的算法包括二分查找。

O(n), 也叫線性時間，這樣的算法包括簡單查找。

O(n * log n), 這樣的算法包括快速排序----一種速度較快的排序算法。

O(n2), 這樣的算法包括選擇排序----一種速度較慢的排序算法。

O(n!), 一直非常慢的算法，類似旅行商問題的解決方案算法。

練習：

(1). 在電話簿中根據名字查找電話号碼。

O(logn)

(2).在電話簿中根據電話号碼找人。（提示：你必須查找整個電話簿。）

O(n)

(3). 閱讀電話簿中每個人的電話号碼。

O(n)

(4).閱讀電話簿中姓名以A打頭的人的電話号碼。這個問題比較棘手，它涉及第4章的概念。答案可能讓你感到驚訝！

O(n)，大O表示法不考慮乘以、除以、加上或減去的

1.7.小結

• 二分查找的速度比簡單查找快的多
• O(log n)比O(n)快。需要搜尋的元素越多，前者比後者就快的越多。
• 算法運作時間并不以秒為機關
• 算法運作時間是從其增速的角度度量的
• 算法運作時間用大O表示法表示