2023 spring Algorithm
week02 homework
Problem Set 2
1. Solve the Problems 34
Q 34. What is the time complexity T(n) of the nested loops below? For simplicity, you may assume that n is a power of 2. That is, n = 2 k for some positive integer k.
Q 34. 아래 중첩 루프의 시간 복잡도 T(n)는 얼마인가? 간단하게, n은 2의 거듭제곱이라고 가정할 수 있다. 즉, 어떤 양의 정수 k에 대해 n = 2 k이다.
my solution)
중첩 루프인 경우, 각각의 루프의 time complexity를 곱한 값이 중첩 루프의 time complexity 이다.
주어진 코드에서 안쪽 루프의 time complexity 는 log2(n) 이고, 바깥쪽 루프의 time complexity는 1/2 log2(n) 이다. 따라서 중첩 루프의 time complexity는 두 time complexity를 곱한 값이므로, log2(n) log2(n) 1/2이고, 로그의 곱셈법칙에 의해 1/2 log2(n+n) 으로 나타낼 수 있다. 이를 정리하면, 최종 time complexity는 O(log2(n))임을 알 수 있다.
provided Solution) T(n) = (log2n + log n)/2 = O(log2n)
difference of solutions)
두번째 로그의 밑의 값이 다르다.
Apply sorting algorithm to the Birthday data set.
생일 데이터에 정렬 알고리즘을 적용시키기
Selection Sort
선택정렬
1) 생일 데이터 array [(11.4), (3.9), ... , (5.31)]생성
2) sorting 실행
a) 가장 생일이 늦은 사람을 가장 맨 뒤로 보내고, 그 자리에 있던 생일은 이동한 생일의 원래 자리로 이동함.
b) 이것을 반복함.
3) Time Complexity
O(n^2)
Merge Sort
합병정렬
1) 생일 데이터 array [(11.4), (3.9), ... , (5.31)]생성
2) sorting 실행
a) 2개의 생일을 짝을 지어 정렬함.
1st try
[(3.9), (11.4), ... , (5.31)]
b) 다시 2묶음씩 짝을 지어 정렬을 반복함.
3) Time Complexity
O(n * log n)
