
Array

- 최악의 경우 전부 n만큼 시간이 걸리기때문에 O(n)
- find의 경우 key값으로 찾는데 왜 n이 걸리는지 모르겠음. -> key:value 와는 다른 개념임. key는 항목을 고유하게 식별하는 값임
arr = [23, 45, 12, 67, 89, 34, 56, 78, 90, 11]
def find(arr, k):
for i in range(len(arr)):
if arr[i] == k:
return arr[i]
return None
result = find(arr, 56)
print(result)
요런 느낌
Sorted Array

- build의 경우 비교 기반 정렬 알고리즘인 적용되는데 이게 O(n log n)이다
- find의 경우 바이너리 서치를 하기 때문에 O(log n)이다.
- sorted array를 생성할때 걸리는 시간은 array보다 비효율적이지만 찾는건 훨씬 빠르다.
Sorting
Permutation Sort
def permutation_sort(A):
’’’Sort A’’’
for B in permutations(A):
if is_sorted(B):
return B
- 가능한 모든 수의 나열 중 sorting된 나열을 찾는 방법
- 모든 가능한 수를 찾는 것 Ω(n!)
- big-o가 아니라 omega인 이유는 적어도 n!를 실행해야함
- 가능한 모든 순열을 생성하는데 걸리는 시간 -> n!, 여기서 찾는 시간 n
- O(n!*n)
- 그중 순서대로 나열되어 있는 것을 찾는다 O(n)
Selection Sort
- 배열을 순회하면서 가장 작은(또는 가장 큰) 원소를 찾아 맨 앞(또는 맨 뒤)으로 이동시키는 방식입니다.
- 이 과정을 배열의 모든 위치에 대해 반복합니다.
8 3 2 9 1
8 3 2 1 9
1 3 2 8 9
1 2 3 8 9
- 공간 복잡도 : S(1)
- 시간 복잡도 : O(n^2)
Merge Sort
7 1 5 6 2 4 9 3
1 7
5 6
- 7 vs 6 -> 7
- 1 vs 6 -> 6
- 1 vs 5 -> 5
- 1
2 4
3 9
- 4 vs 9 -> 9
- 4 vs 3 -> 4
- 2 vs 3 -> 3
- 2
1 5 6 7
2 3 4 9
- 7 vs 9 -> 9
- 7 vs 4 -> 7
- 6 vs 4 -> 6
- 5 vs 4 -> 5
- 1 vs 4 -> 4
- 1 vs 3 -> 3
- 1 vs 2 -> 2
- 1