Complexity Analysis of Algorithms
Open Problem 1
Compare the efficiency of the below two algorithms, visually or theoretically or in your way!
알고리즘 1에서는 n^(7/5) 항이 n의 증가에 따라 가장 빠르게 증가한다.
알고리즘 2에서는 n^(11/6) 항이 n이 지배적이다.
각 최고차항의 지수를 비교했을 때 2의 n^(11/6)이 1보다 크다.
➡️ n이 커질수록 알고리즘 2의 실행시간이 알고리즘 1보다 더 빠르게 증가하므로, 알고리즘 1이 알고리즘 2보다 효율적이다.
Open Problem 2
Find the time complexity of the following Python code and explain:
i=1
while(i<n):
i*=2
print("data")i가 1에서 시작해서 i가 n보다 작은 동안 i의 값을 2배씩 증가시키는 반복문
매 반복마다 data 출력함.
- 반복문은 i의 값이 매 반복마다 2배로 증가하기 때문에, n에 도달하기 위해 필요한 반복 횟수는 n의 크기에 따라 로그 스케일로 증가함.
- i는 1, 2, 4, 8, ... 과 같이 증가하고 n에 도달하거나 넘기 위해서는 log작은2n 번의 반복이 필요함.
➡️ 시간 복잡도는 O(logn)
n이 커질수록 실행시간이 로그 함수의 증가율로 증가함을 의미한다. while 반복문은 i가 n을 초과할 때까지 반복됨.
Open Problem 3
Find the time complexity of the following Python code and explain:
i = n
while(i>0):
print("complexity")
i /= 2i가 0보다 큰 동안 i의 값을 2로 나누는 반복문을 포함한다. 매 반복마다 complexity 출력됨.
- 반복문은 i의 값이 매 반복마다 절반으로 감소하기 때문에 i가 0보다 작아지기까지 필요한 반복 횟수는 n의 크기에 따라 로그 스케일로 증가한다.
- i는 n, n/2, n/4, ... 과 같이 감소하며 0에 도달하거나 그보다 작아지기 위해서는 log작은2n번의 반복이 필요하다.
➡️ 시간 복잡도는 O(logn)
Open Problem 4
Find the time complexity of the following Python code and explain:
for i in range(1,n):
j = i
while(j<n):
j*=2for 루프는 1부터 n-1까지 반복하고, while 루프는 j가 n 미만일 때까지 j의 값을 2배로 증가시킨다. 여기서 j는 for 루프이ㅡ 각 반복마다 i로 초기화된다.
- for 루프는 n-1번 반복해서 O(n)의 시간복잡도를 가진다.
- while 루프에서는 j가 매번 2배씩 증가하기 때문에, i부터 n에 도달하기까지의 반복횟수는 log작은2n에 비례한다. 따라서 while 루프의 시간 복잡도는 O(logn)이다.
- 총 시간 복잡도는 for와 while의 결합이다.
➡️ 시간복잡도는 O(nlogn)
Open Problem 5
Find the time complexity of the following Python code and explain:
i=1
while(i<n):
print("python")
i = i**2i가 1에서 시작해서 i가 n보다 작은 동안 i의 값을 i제곱하는 반복문
- while 루프는 i의 값이 매 반복마다 제곱되기 때문에 i가 n에 도달하기까지 필요한 반복 횟수는 n의 크기에 따라 로그 로그 스케일로 증가한다.
엥?
계속 1이면..무한..?
Recursion
Open Problem 1
In the lecture slide, we showed the time complexity of the below algorithm for Fibonacci series is O(2^n). In similar way, find Big Omega Ω(⋅) of this algorithm.
# Recursion
def fib_recursive(n):
if n < 0:
print("Incorrect input")
elif n == 0:
return 0
elif n == 1 or n == 2:
return 1
else:
return fib_recursive(n-1)+fib_recursive(n-2)Ω는 알고리즘의 최소 실행 시간이나 하한을 나타내는 데 사용됨.
Big O을 통해 최악의 시간 복잡도가 O(2^n)이라는 것을 알 수 있음. 그러나 피보나치 수열을 계산하는 알고리즘 특성상 각 단계에서 재귀 호출이 이루어지고, 이 호출이 연속적으로 이루어지므로 성능 하한도 지수임.
➡️ Ω(2^n)
Open Problem 2
Can you write an algorithm for the Fibonacci series with a time complexity of O(n)?
def fib_dynamic(n):
# n이 0이거나 음수인 경우의 처리
if n < 0:
print("Incorrect input")
return None
# n이 0 또는 1인 경우의 처리
elif n == 0:
return 0
elif n == 1:
return 1
# 첫 번째 항과 두 번째 항의 초기 값 설정
fib_0, fib_1 = 0, 1
# n번째 항까지 계산
for i in range(2, n + 1):
fib_n = fib_0 + fib_1
fib_0, fib_1 = fib_1, fib_n
return fib_n
print(fib_dynamic(10)) # 10번째 피보나치 수를 출력Open Problem 3
- Write functions that calculates the factorial of n (i.e., n!)
- Approach 1: Using For loop
- Approach 2: Using Recursive algorithm
- Time complexity analysis
- Provide comparison of both practical (e.g. for n=100) and theoretical time complexity analysis for each approach
1. Approach 1: Using For loop
def factorial_for_loop(n):
if n < 1: # 0! = 1
return 1
result = 1
for i in range(1, n + 1):
result *= i
return result- 1부터 n까지 의 수에 대해 1번씩 곱셈 수행함.
- 시간 복잡도는 O(n)
(n에 대해 선형적으로 증가하는 연산 횟수를 가짐.)
2. Approach 2: Using recursive algorithm
def factorial_recursive(n):
if n < 1: # 0! = 1
return 1
else:
return n * factorial_recursive(n - 1)- 각 단계에서 n에 대한 곱셈을 한 번 수행하고 n-1에 대해 자신을 호출함.
n에서 1까지 감소하면서 각 단계마다 한 번의 호출이 발생하므로 시간 복잡도는 O(n).
n = 100과 같은 상대적으로 큰 값에 대해서는 for 루프 방식이 재귀 방식보다 선호될 수 있음. 재귀 방식은 호출 스택의 크기에 제한이 있기 때문에, 매우 깊은 재귀 호출이 필요한 경우 스택 오버플로우 오류가 발생할 수 있음.
Open Problem 4
Write an recursive algorithm that prints out multiplication table (i.e., gugu-dan). For example, “Table of 3” should print out the below.
## 3 x 1 = 3
## 3 x 2 = 6
## 3 x 3 = 9
## 3 x 4 = 12
## 3 x 5 = 15
## 3 x 6 = 18
## 3 x 7 = 21
## 3 x 8 = 24
## 3 x 9 = 27def print_multiplication_table(number, i=1):
if i > 9: # 기저 조건: i가 9보다 크면 종료
return
print(f"{number} x {i} = {number * i}")
print_multiplication_table(number, i + 1) # 재귀 호출: 다음 곱셈을 출력
# 예제: 3의 구구단 출력
print_multiplication_table(3)
Open Problem 5
Write an algorithm that convert the given decimal number into an equivalent binary number. For example, The decimal number 10 can be represented as the binary number 1010.
## Decimal number = 10 can be represented as the Binary number 1010
10진수를 2진수로 변환하는 알고리즘 작성
1. 주어진 10진수 n을 2로 나눈다.
2. 나머지를 결과 문자열에 추가한다.
3. n을 2로 나눈 몫으로 업데이트하고 1단계로 돌아간다.
4. n이 0이 될 때까지 이 과정 반복한다.
5. 마지막으로 결과 문자열을 뒤집는다. (나머지 구하는 과정에서 2진수의 가장 낮은 자리수부터 계산하기 때문)
코드 예시
def decimal_to_binary(n):
# 기저 조건: n이 0이면, 빈 문자열을 반환
if n == 0:
return "0"
# 재귀적으로 나머지를 문자열로 변환하여 결합
else:
return decimal_to_binary(n // 2) + str(n % 2) if n > 1 else str(n % 2)
# 예제: 10을 이진수로 변환
binary_number = decimal_to_binary(10)
# 앞에 "0"이 올 경우를 대비하여 int로 변환 후 다시 str로 변환하여 불필요한 "0" 제거
binary_number = str(int(binary_number))
print(f"Decimal number = 10 can be represented as the Binary number {binary_number}")10진수를 2진수로 변환하는 재귀함수 decimal_to_binary를 정의한다. 함수는 10진수 n을 인수로 받아, 이를 2진수 문자열로 변환하여 반환한다. n이 0이면 0을 반환하고, 1 이상이면 n을 2로 나눈 몫을 함수에 다시 넘기고 현재의 n을 2로 나눈 나머지를 문자열에 추가한다. 이 과정을 n이 0이 될 때까지 반복하고 최종적으로 생성된 문자열을 반환한다.
Open Problem 6
- Suppose there is a given number, n (i.e. 12).
- If that given number is even, you half that number. You continue to half the resulting number if it is even.
- If not (i.e., if the number is odd), then you take the odd number and multiply it by 3 and add 1.
- You continue to apply these two operations (either n∗2 or 3n+1) until n = 1.
- For example,
- Say n=20. Then 20−>10−>5−>16−>8−>4−>2−>120−>10−>5−>16−>8−>4−>2−>1
- Say n=32. Then 32−>16−>8−>4−>2−>132−>16−>8−>4−>2−>1
- Write algorithms that using For loop or recursive algorithm.
- What is this conjecture and any interesting story?
콜라츠 추측. 어떤 자연수 n에 대해서도 다음 규칙을 반복하면 최종적으로 1에 도달한다.
- 이 짝수라면, 을 2로 나눈다.
- 이 홀수라면, 에 3을 곱하고 1을 더한다.
- 이 과정을 이 1이 될 때까지 반복한다.
For loop 사용한 알고리즘
def collatz_for_loop(n):
sequence = [n] # 초기 수 n을 시퀀스에 포함
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
sequence.append(n)
return sequence
Recursive Algorithm
def collatz_recursive(n, sequence=None):
if sequence is None:
sequence = [n]
if n == 1:
return sequence
elif n % 2 == 0:
sequence.append(n // 2)
return collatz_recursive(n // 2, sequence)
else:
sequence.append(3 * n + 1)
return collatz_recursive(3 * n + 1, sequence)