MIT algorithm lecture - 3. Sets and Sorting

CH_Hwang·2024년 8월 18일
0

MIT

목록 보기
2/4

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)  # 출력: 56 (찾은 항목 자체를 반환)

요런 느낌

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): # O(n!)
		if is_sorted(B): # O(n)
			return B # O(1)
  • 가능한 모든 수의 나열 중 sorting된 나열을 찾는 방법
    • 모든 가능한 수를 찾는 것 Ω(n!)
      - big-o가 아니라 omega인 이유는 적어도 n!를 실행해야함
      • 가능한 모든 순열을 생성하는데 걸리는 시간 -> n!, 여기서 찾는 시간 n
      • O(n!*n)
    • 그중 순서대로 나열되어 있는 것을 찾는다 O(n)

Selection Sort

  1. 배열을 순회하면서 가장 작은(또는 가장 큰) 원소를 찾아 맨 앞(또는 맨 뒤)으로 이동시키는 방식입니다.
  2. 이 과정을 배열의 모든 위치에 대해 반복합니다.

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,75,62,43,9

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,72,3,4,9

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
  • 시간 복잡도 : O(n log n)

0개의 댓글

Powered by GraphCDN, the GraphQL CDN