算法

• 大整数乘法 Karatsuba’s Algorithm

j = 13579246801593726048
k = 24680135792604815937

def karatsuba_multiply(j,k):
    n = int(len(str(min(j,k)))/2)
    if n==0 or j<10 or k<10:
        return j*k
    
    print(n)
    a, b = int(j/(10**n)), int(j%(10**n))
    c, d = int(k/(10**n)), int(k%(10**n))
    
    ac = karatsuba_multiply(a,c)   # a*c
    bd = karatsuba_multiply(b,d)   # b*d
    a_b_c_d = karatsuba_multiply((a+b),(c+d))   # (a+b)*(c+d)

    ad_bc = a_b_c_d - ac - bd  ## ad+bc
    return ac*(10**(2*n)) + ad_bc*(10**n) +bd

• Select K 从列表中选择第k个最小的数 （索引从零开始） n-1+log(n) 次比较

### Select-k algorithm   比较的次数是 n-1 +log(n)     复杂度是多少？？？

···
#### 简单的查找
def merge_sort(lst):
    ## 由小到大排序列表, merge sort
    print(len(lst))
    if len(lst)<=1:
        return lst
    L,R = lst[:len(lst)//2], lst[len(lst)//2:]
    L = merge_sort(L)
    R = merge_sort(R)
    
    i,j=0,0   ### 将两个有序列表进行合并
    out = []
    while i<len(L) and j<len(R):
        if L[i]<=R[j]:
            out.append(L[i])
            i+=1
        else:
            out.append(R[j])
            j+=1
    out +=L[i:]+R[j:]
    return out
        

### runtime O(n logn)
def naive_select_k(lst, k):
    ##选择第k小的数
    lst = merge_sort(lst)
    return lst[k]
···


def partition(lst,  p):
    """
    按index p分成左右两部分
    """
    L, R = [], []
    for i in range(len(lst)):
        if i==p:
            continue
        
        L.append(lst[i]) if lst[i]<=lst[p] else R.append(lst[i])
    
    return L, lst[p], R  # 列表， 元素，列表    小--》大


def select_k(lst, k):
    if len(lst)==1:
        return lst[0]
    
    L, item, R = partition(lst, int(len(lst)/2))
    if len(L) == k:
        return item ## 前面的元素有k个，则索引为k的元素正是 item
    elif len(L) >k:
        return select_k(L,k)
    elif len(L)<k:
        return select_k(R, k-len(L)-1)