Open5
アルゴリズムの勉強メモ
kzrashi最大公約数(Greatest Common Divisor)を求めるアルゴリズム1
1. Overview
最大公約数とは、複数の数のうち、最大の約数のこと
例)50と75の最大公約数は25
2.アルゴリズム
pythonで記述する
2.1. 手法1(単純に１つずつ割って求めていく)
num1 = 50
num2 = 75
# num1側に大きな数をもってくる
if num1 < num2:
num1,num2 = num2,num1
# 小さい方の数を割る数に持ってくる
gcd = num2
while True:
# 両方割り切れたら、その数が最大公約数になる
if num1 % gcd == 0 and num2 % gcd == 0:
break
# 割り切れない場合、１ずつ減らして再計算する
gcd -= 1
# 結果出力
print("gcd=",gcd)
2022/01/30
種類
検索アルゴリズム
アルゴリズム名
線形サーチ(Linear Search)
特徴
- 単純に配列の先頭から検索していくアルゴリズム
- 事前にソートされていなくてよい
計算時間(Time Conplexity)
O(n)
メモリ使用量(Space Complexity)
アルゴリズム
python
def linear_search(nums:List[int], x:int)->bool:
"""
配列内に対象の数値が存在するか検索する。
Parameters
----------
nums : List[int]
検索対象の配列
x : int
検索する数値
Returns
-------
is_found : bool
存在する場合、trueを返却する
"""
for num in nums:
if x == num:
# found x in nums
return True
# not found x in nums
return False
#---------------------------------------
# ここからメイン関数
if __name__ == "__main__":
nums = [1,3,5,7,10]
# 存在する数値
print(linear_search(nums, 3))
# 存在しない数値
print(linear_search(nums, 9))
2022/01/30
種類
ソートアルゴリズム
アルゴリズム名
選択ソート(selection Sort)
特徴
- 先頭から全データを比較して並び替えを行うアルゴリズム
- めちゃくちゃ遅い
計算時間(Time Conplexity)
O(n×n)
メモリ使用量(Space Complexity)
アルゴリズム
python
import copy
def selection_sort(nums:List[int])->List[int]:
"""
配列を選択ソートアルゴリズムでソートする
Parameters
----------
nums : List[int]
ソート対象の配列
Returns
-------
ret_nums] List[int]
ソート後の配列
"""
s_nums = copy.copy(nums)
s_len = len(s_nums)
for i in range(s_len):
min_idx = i
for j in range(i,s_len):
if s_nums[min_idx] > s_nums[j]:
min_idx = j
#
s_nums[i],s_nums[min_idx] = s_nums[min_idx], s_nums[i]
return s_nums
#---------------------------------------
# ここからメイン関数
if __name__ == "__main__":
nums = [20,4,1,40,15]
print(selection_sort(nums))
2022/01/30
種類
ソートアルゴリズム
アルゴリズム名
マージソート(merge Sort)
特徴
- 細かい単位分割＆ソートを繰り返して結合していくアルゴリズム
計算時間(Time Conplexity)
O(nLog n)
メモリ使用量(Space Complexity)
アルゴリズム
python
import random
import copy
def m_sort(nums1:List[int], nums2:List[int])-> List[int]:
idx1,idx2=0,0
ret_nums = list()
while idx1 < len(nums1) and idx2 < len(nums2):
if nums1[idx1] < nums2[idx2]:
ret_nums.append(nums1[idx1])
idx1 += 1
else:
ret_nums.append(nums2[idx2])
idx2 += 1
# pythonでは範囲外のスライスは無視される
return ret_nums + nums1[idx1:] + nums2[idx2:]
def split_nums(nums:List[int])-> List[int]:
s_nums = [[num] for num in nums]
while len(s_nums) > 1:
tmp_nums = list()
for i in range(0,len(s_nums),2):
if (i+1) == len(s_nums):
tmp_nums.append(s_nums[i])
else:
tmp_nums.append(m_sort(s_nums[i], s_nums[i+1]))
s_nums = [tmp_nums[i] for i in range(len(tmp_nums))]
return s_nums[0]
# ここからメイン関数
if __name__ == "__main__":
random.seed(10)
nums = [random.randint(0,1000) for i in range(10)]
print(nums)
print(split_nums(nums))
2022/01/31
種類
ソートアルゴリズム
アルゴリズム名
クイックソート(Quick Sort)
特徴
- マージソートと似ているが、計算量にブレが発生するアルゴリズム
計算時間(Time Conplexity)
O(nLog n)～O(n×n)
メモリ使用量(Space Complexity)
アルゴリズム
python
import random
def my_quick_sort(nums:List[int])-> List[int]:
if nums == []:
return nums
p = random.choice(nums)
left = list()
right = list()
pivots = list()
for num in nums:
if num < p:
left.append(num)
elif num == p:
pivots.append(num)
else:
right.append(num)
return my_quick_sort(left) + pivots + my_quick_sort(right)
# ここからメイン関数
if __name__ == "__main__":
random.seed(10)
nums = [random.randint(0,1000) for i in range(10)]
print(nums)
print(my_quick_sort(nums))