- 大整數乘法 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)
