about algorithms
Table of Contents

求最大公约数

欧几里得方法

def gcd(p, q):
    if q == 0:
        return p
    else:
        r = p % q
        return gcd(q, r)

素数的判断

小于 2 肯定不是，大于 2 ，从 2 到检查的数的平方根，能被整除则是素数，否则不是。

二分查找

def binary_sort(array, key, start, end):
    if start > end:
        return -1
    middle = (start + end) // 2
    if key < array[middle]:
        return binary_sort(array, key, start, middle-1)
    elif key > array[middle]:
        return binary_sort(array, key, middle+1, end)
    else:
        return middle

时间复杂度

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)