# 한글 폰트 사용을 위한 코드입니다.
import sys
# 코랩의 경우 나눔 폰트를 설치합니다.
if 'google.colab' in sys.modules:
!sudo apt-get -qq -y install fonts-nanum
import matplotlib.font_manager as fm
font_files = fm.findSystemFonts(fontpaths=['/usr/share/fonts/truetype/nanum'])
for fpath in font_files:
fm.fontManager.addfont(fpath)
# 나눔 폰트를 사용합니다.
import matplotlib
matplotlib.rc('font', family='NanumBarunGothic')
matplotlib.rcParams['axes.unicode_minus'] = False
def f(i):
"""i는 int이고 i >= 0라고 가정합니다"""
answer = 1
while i >= 1:
answer *= i
i -= 1
return answer
def linear_search(L, x):
for e in L:
if e == x:
return True
return False
def fact(n):
"""n은 양의 정수라고 가정합니다.
n!을 반환합니다"""
answer = 1
while n > 1:
answer *= n
n -= 1
return answer
예제 11-1 완전 열거를 사용해 제곱근의 근삿값 찾기
def square_root_exhaustive(x, epsilon):
"""x와 epsilon은 양의 실수이고 epsilon < 1이라고 가정합니다.
x에서 epsilon 이내에 y*y가 있을 때 y를 반환합니다"""
step = epsilon**2
ans = 0.0
while abs(ans**2 - x) >= epsilon and ans*ans <= x:
ans += step
if ans*ans > x:
raise ValueError
return ans
예제 11-2 이분 검색을 사용해 제곱근의 근삿값 찾기
def square_root_bi(x, epsilon):
"""x와 epsilon은 양의 실수이고 epsilon < 1이라고 가정합니다.
x에서 epsilon 이내에 y*y가 있을 때 y를 반환합니다"""
low = 0.0
high = max(1.0, x)
ans = (high + low)/2.0
while abs(ans**2 - x) >= epsilon:
if ans**2 < x:
low = ans
else:
high = ans
ans = (high + low)/2.0
return ans
예제 11-3 점근 복잡도
def f(x):
"""x는 0보다 큰 정수라고 가정합니다"""
ans = 0
#상수 시간이 걸리는 루프
for i in range(1000):
ans += 1
print('지금까지 덧셈 횟수:', ans)
#x 시간이 걸리는 루프
for i in range(x):
ans += 1
print('지금까지 덧셈 횟수:', ans)
#x**2 시간이 걸리는 중첩 루프
for i in range(x):
for j in range(x):
ans += 1
ans += 1
print('지금까지 덧셈 횟수:', ans)
return ans
f(10)
지금까지 덧셈 횟수: 1000 지금까지 덧셈 횟수: 1010 지금까지 덧셈 횟수: 1210
1210
f(1000)
지금까지 덧셈 횟수: 1000 지금까지 덧셈 횟수: 2000 지금까지 덧셈 횟수: 2002000
2002000
뇌풀기 문제
def g(L, e):
"""L은 정수 리스트이고 e는 정수입니다"""
for i in range(100):
for e1 in L:
if e1 == e:
return True
return False
def h(L, e):
"""L은 정수 리스트이고 e는 정수입니다"""
for i in range(e):
for e1 in L:
if e1 == e:
return True
return False
g(L,e)의 복잡도는 O(len(L)), h(L,e)의 복잡도는 O(e*len(L)).
def int_to_str(i):
"""i는 0보다 큰 정수라고 가정합니다.
i의 문자열 표현을 반환합니다"""
digits = '0123456789'
if i == 0:
return '0'
result = ''
while i > 0:
result = digits[i%10] + result
i = i//10
return result
def add_digits(n):
"""n이 0보다 큰 정수라고 가정합니다.
n에 있는 숫자의 합을 반환합니다"""
string_rep = int_to_str(n)
val = 0
for c in string_rep:
val += int(c)
return val
def add_digits(s):
"""s는 숫자 문자열이라고 가정합니다.
s에 있는 숫자의 합을 반환합니다"""
val = 0
for c in string_rep:
val += int(c)
return val
def factorial(x):
"""x는 양의 정수라고 가정합니다.
x!를 반환합니다"""
if x == 1:
return 1
else:
return x*factorial(x-1)
예제 11-4 부분집합 테스트 함수
def is_subset(L1, L2):
"""L1과 L2는 리스트로 가정합니다.
L1의 모든 원소가 L2에도 있으면 True, 그렇지 않으면 False를 반환합니다"""
for e1 in L1:
matched = False
for e2 in L2:
if e1 == e2:
matched = True
break
if not matched:
return False
return True
예제 11-5 두 리스트의 교집합 구하기
def intersect(L1, L2):
"""가정: L1와 L2는 리스트입니다.
L1과 L2의 교집합을 반환합니다"""
#공통 원소를 담은 리스트를 만듭니다
tmp = []
for e1 in L1:
for e2 in L2:
if e1 == e2:
tmp.append(e1)
break
#중복이 없는 리스트 만들기
result = []
for e in tmp:
if e not in result:
result.append(e)
return result
예제 11-6 멱집합 생성하기
def get_binary_rep(n, num_digits):
"""n과 num_digits은 음수가 아닌 정수로 가정합니다.
n의 이진 표현을 num_digits 길이의 문자열로 반환합니다"""
result = ''
while n > 0:
result = str(n%2) + result
n = n//2
if len(result) > num_digits:
raise ValueError('num_digits가 부족합니다')
for i in range(num_digits - len(result)):
result = '0' + result
return result
def gen_powerset(L):
"""L은 리스트로 가정합니다.
L에 있는 원소로 가능한 모든 조합을 담은 리스트의 리스트를 반환합니다.
예를 들어 L이 [1, 2]이면 [], [1], [2], [1, 2]를 원소로 가진 리스트를 반환합니다"""
powerset = []
for i in range(0, 2**len(L)):
bin_str = get_binary_rep(i, len(L))
subset = []
for j in range(len(L)):
if bin_str[j] == '1':
subset.append(L[j])
powerset.append(subset)
return powerset
그림 11-7 상수, 로그, 선형 복잡도
import matplotlib.pyplot as plt
import math
x_vals = range(1, 100000, 1)
y_const, y_log = [], []
for x in x_vals:
y_const.append(15)
y_log.append(math.log2(x))
plt.plot(x_vals, y_const, 'r--', label = '상수')
plt.plot(x_vals, y_log, 'k-', label = '로그')
plt.xlabel('입력 크기')
plt.ylabel('시간')
plt.title('상수 (15) vs. (밑이 2인) 로그')
plt.legend()
plt.figure()
x_vals = range(1, 100000, 1)
y_log, y_linear = [], []
for x in x_vals:
y_linear.append(x)
y_log.append(math.log2(x))
plt.plot(x_vals, y_linear, 'r--', label = '선형')
plt.plot(x_vals, y_log, 'k-', label = '로그')
plt.xlabel('입력 크기')
plt.ylabel('시간')
plt.title('(밑이 2인) 로그 vs. 선형')
plt.legend()
plt.show()
그림 11-8 선형, 로그-선형, 다항 복잡도
plt.figure()
x_vals = range(1, 1000, 1)
y_log_linear, y_linear = [], []
for x in x_vals:
y_linear.append(x)
y_log_linear.append(x*math.log2(x))
plt.plot(x_vals, y_linear, 'r--', label = '선형')
plt.plot(x_vals, y_log_linear, 'k-', label = '로그-선형')
plt.xlabel('입력 크기')
plt.ylabel('시간')
plt.title('선형 vs. 로그-선형')
plt.legend()
plt.figure()
x_vals = range(1, 1000, 1)
y_log_linear, y_quadratic = [], []
for x in x_vals:
y_quadratic.append(x**2)
y_log_linear.append(x*math.log2(x))
plt.plot(x_vals, y_quadratic, 'r--', label = '2차 다항식')
plt.plot(x_vals, y_log_linear, 'k-', label = '로그-선형')
plt.xlabel('입력 크기')
plt.ylabel('시간')
plt.title('로그-선형 vs. 2차 다항식')
plt.legend()
plt.show()
그림 11-9 2차 다항식과 지수 복잡도
plt.figure()
x_vals = range(1, 100, 1)
y_quad, y_exp = [], []
for x in x_vals:
y_quad.append(x**2)
y_exp.append(2**x)
plt.plot(x_vals, y_quad, 'r--', label = '2차 다항식')
plt.plot(x_vals, y_exp, 'k-', label = '지수')
plt.xlabel('?입력 크기')
plt.ylabel('시간')
plt.title('2차 다항식 vs. 지수')
plt.legend()
plt.figure()
x_vals = range(1, 100, 1)
y_quad, y_exp = [], []
for x in x_vals:
y_quad.append(x**2)
y_exp.append(2**x)
plt.plot(x_vals, y_quad, 'r--', label = '2차 다항식')
plt.plot(x_vals, y_exp, 'k-', label = '지수')
plt.xlabel('입력 크기')
plt.ylabel('시간')
plt.title('2차 다항식 vs. 지수')
plt.legend()
plt.semilogy()
plt.show()
/usr/local/lib/python3.9/dist-packages/IPython/core/pylabtools.py:151: UserWarning: Glyph 8 () missing from current font. fig.canvas.print_figure(bytes_io, **kw)