리스트 길이가 몇이든 가장 앞에있는 요소를 받아오기떄문에 O(1)이다.
def print_first(my_list):
print(my_list[0])
print_first([2, 3])
print_first([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53])
리스트 길이인 N만큼 시행횟수를 반복하기 떄문에 O(n)이다
# O(n) 함수
def print_each(my_list):
for i in range(len(my_list)):
print(my_list[i])
N/2만큼 반복해서 O(n)이다.
# O(n) 함수
def print_half(my_list):
for i in range(len(my_list) // 2):
print(my_list[i])
O(3n)임으로 O(n)이다.
# O(n) 함수
def print_three_times(my_list):
for i in range(len(my_list)):
print(my_list[i])
for i in range(len(my_list)):
print(my_list[i])
for i in range(len(my_list)):
print(my_list[i])
이중 for문 같은 경우 O(n^2)이다.
# O(n^2) 함수
def print_pairs(my_list):
for i in range(len(my_list)):
for j in range(len(my_list)):
print(my_list[i], my_list[j])
삼중 for문 같은 경우 O(n^3)이다.
# O(n^3) 함수
def print_triplets(my_list):
for i in range(len(my_list)):
for j in range(len(my_list)):
for k in range(len(my_list)):
print(my_list[i], my_list[j], my_list[k])
1에서 2배로 lg n
만큼 늘려나가면 n이 된다.
# O(lg n) 함수
# 2의 거듭제곱을 출력하는 함수
# (이번에는 인풋이 리스트가 아니라 그냥 정수입니다)
def print_powers_of_two(n):
i = 1
while i < n:
print(i)
i = i * 2
n을 몇번 반토막을 내야 1이되냐면 lg n
만큼이다.
# O(lg n) 함수
# 2의 거듭제곱을 출력하는 함수
# (이번에는 인풋이 리스트가 아니라 그냥 정수입니다)
def print_powers_of_two(n):
i = n
while i > 1:
print(i)
i = i / 2
for 문안에서 some_list의 개수만큼 돌아감으로 시간복잡도는 O(N)이다.
def linear_search(element, some_list):
for i in range(len(some_list)):
if element == some_list[i]:
return i
이진탐색은 최악의 경우 N길이의 리스트를 lgN만큼 반복한다.
def binary_search(element, some_list):
start_index, end_index = 0, len(some_list) - 1
while start_index <= end_index:
mid_index = (start_index + end_index) // 2
if some_list[mid_index] == element:
return mid_index
elif some_list[mid_index] < element:
start_index = mid_index + 1
elif some_list[mid_index] > element:
end_index = mid_index - 1
return None
log는 좀 헷갈리는 개념인데
Log_a(b)
는
b를 a로 몇번 나눠야하 되나?
라고 생각하면 될꺼같다.
예를들어 log_2(N)은
N길이의 리스트를 몇번 반토막 내야 1(최악의 경우 자료의 길이는 1이 됨으로)이 될 수 있나?
라고 생각하면 된다
보통 log_2(N)은 lgN이라고 사용한다.
result 는 O(1)이다.
def product(a, b, c):
result = a * b * c
return result
every_other의 공간복잡도는 O(n/2)여서 O(n)이다.
def get_every_other(my_list):
every_other = my_list[::2]
return every_other
a,b는 정수값임으로 O(1)이다.
products의 공간복잡도는 O(n^2)이다.
def largest_product(my_list):
products = []
for a in my_list:
for b in my_list:
products.append(a * b)
return max(products)