: 알고리즘을 이용하여 어떤 원소가 리스트 안에 포함되어 있는 지 확인
: 리스트의 처음부터 끝까지 순서대로 하나씩 탐색 진행
-시간 복잡도 → O(n)
<선형탐색 스스로 만들어보기>
def linear_search(element, some_list):
for i in range(len(some_list)):
if some_list[i] == element:
return i
print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))
0
None
2
1
4
→ continue써줘야 하는지 헷갈렸지만, 조건을 만족하는 경우 바로 조건확인 끝나는 탐색이므로 continue사용 안해도 됨
-정렬된 리스트를 전제로함. 중간값을 먼저 찾아 탐색범위를 반씩 줄여나가는 알고리즘
-시간 복잡도 → O(lg n)
<나의 첫번째 코드->실패!>
def binary_search(element, some_list):
last_index = len(some_list)
if last_index % 2 == 1: # 리스트가 홀수길이라면?
avg_index = len(some_list) // 2
while avg_index > 0:
if some_list[avg_index] == element:
return avg_index
elif some_list[avg_index] >> element:
del some_list[avg_index : last_index - 1]
else:
del some_list[0 : avg_index]
elif last_index % 2 == 0:
avg_index = (len(some_list) // 2) - 1
while avg_index > 0:
if some_list[avg_index] == element:
return avg_index
elif some_list[avg_index] >> element:
del some_list[avg_index : last_index - 1]
else:
del some_list[0 : avg_index]
→ 일단 홀수 길이, 짝수 길이에서 벗어나 변수 다시 지정하기.
→ 리스트 자르는 방법에서 계속되는 벗어남 문제 → 자르지 않고 포인트 다시 지정해주기
<모범 코드>
def binary_search(element, some_list):
start_index = 0
end_index = len(some_list) - 1
while start_index <= end_index:
midpoint = (start_index + end_index) // 2
if some_list[midpoint] == element:
return midpoint
elif some_list[midpoint] > element:
end_index = midpoint - 1
else:
start_index = midpoint + 1
return None
print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))
-리스트의 원소들을 특정 순서로 정리하는 것
-가장 먼저 생각날 수 있는 자연스러운 정렬 알고리즘
-순서대로 탐색해서 가장 작은 값을 찾아서 0번 인덱스에 놓고, n번째로 작은 값을 찾아서 n번 인덱스에 넣음(찾은 최솟값을 n번 인덱스로 옮김)
-각 값이 어떤 위치에 들어갈지 찾음
-알고리즘 분석에서 시간복잡도(Time complexity)에 사용되는 방법, 절대적인 시간보다 성장성에 의미를 둔다.
-그래프 : 꼭지점(vertex)과 변(edge)로 이루어져있음. 꼭지점의 개수를 V라고 하고, 변의 개수를 E라고 하면 두 꼭지점 간 최단경로를 찾는 BFS알고리즘의 시간복잡도는 O(V + E)
-리스트의 길이가 n일 때
Operation | Code | Average Case |
---|---|---|
인덱싱 | my_list[index] | O(1) |
정렬 | my_list.sort()sorted(my_list) | O(n\lg{n} |
뒤집기 | my_list.reverse() | O(n) |
탐색 | element in my_list | O(n) |
끝에 요소 추가 | my_list.append(element) | O(1) |
중간에 요소 추가 | my_list.insert(index, element) | O(n) |
삭제 | del my_list[index] | O(n) |
최솟값, 최댓값 찾기 | min(my_list)max(my_list) | O(n) |
길이 구하기 | len(my_list) | O(1) |
슬라이싱 | my_list[a:b] | O(b - a) |
Operation | Code | Average Case |
---|---|---|
값 찾기 | my_dict[key] | O(1) |
값 넣어주기/덮어쓰기 | my_dict[key] = value | O(1) |
값 삭제 | del my_list[key] | O(1) |
# 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])
# O(1)은 인풋의 크기가 소요 시간에 영향이 없다는 뜻
# 두 번째 호출할 때는 요소가 16개 있는 리스트를 넘겨줬지만 사실 두 경우 걸리는 시간은 거의 똑같음
# 어차피 맨 앞에 있는 요소를 받아오는 것 뿐이니까, 리스트의 길이는 상관X
# 예시 1
def print_each(my_list):
for i in range(len(my_list)):
print(my_list[i])
# 반복문이 있고, 반복되는 횟수가 인풋의 크기와 비례하면 일반적으로 O(n)
# 예시 2
def print_half(my_list):
for i in range(len(my_list) // 2):
print(my_list[i])
# n번 반복하는 게 아니라 n/2번 반복하면 O(1/2n)이지만, 1/2을 버려서 결론적으로 O(n)
# 예시 3
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])
# O(3n)인데, 결국에는 3을 버려서 이것 또한 O(n)
# 예시 1
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])
# 예시처럼 두 반복문 다 인풋의 크기에 비례하는 경우 O(n^2)
# 예시 1
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])
# O(n^2)와 동일한 원리로 인풋에 크기에 비례하는 반복문이 세 번 중첩되면 O(n^3)
# 예시 1
# 2의 거듭제곱을 출력하는 함수
# 이번에는 인풋이 리스트가 아니라 그냥 정수
def print_powers_of_two(n):
i = 1
while i < n:
print(i)
i = i * 2
# 인풋 n이 128이면 i가 1일 때부터 2, 4, 8, 16, 32, 64까지 총 7번 실행 -> O(lg n)
# 예시 2
def print_powers_of_two(n):
i = n
while i > 1:
print(i)
i = i / 2
# 예시 1과 비슷한 원리로 O(lg n)
# 예시 1
def print_powers_of_two_repeatedly(n):
for i in range(n): # 반복횟수: n에 비례
j = 1
while j < n: # 반복횟수: lg n에 비례
print(i, j)
j = j * 2
# for문의 반복횟수는 n에 비례하는데, while문의 반복횟수는 lg{n}에 비례
# while문이 for문 안에 중첩되어 있기 때문에 위 코드의 시간 복잡도는 O(n lg n)
# 예시 2
def print_powers_of_two_repeatedly(n):
i = 1
while i < n: # 반복횟수: lg n에 비례
for j in range(n): # 반복횟수: n에 비례
print(i, j)
i = i * 2