1. 좋은 알고리즘이란?

1. 리스트에서 값 찾기

• 선형 탐색 알고리즘(Linear search algorithm)
• 이진 탐색 알고리즘(binary search algorithm)
  • 정렬된 데이터 기반. 리스트의 길이가 길어져도! 검색할 요소의 개수가 천천히 증가한다.

#이진탐색
def binary_search(element, some_list): 
	start_index = 0 
	end_index = len(some_list) - 1 

	while start_index <= end_index: 
		# start_index 가 커지는 경우가 있으므로 (start_index + end_index) // 2 
		mid_index = (start_index + end_index) // 2 
			# element 가 mid_index 값과 같으면 return mid_index 
		if element == some_list[mid_index]: 
			return mid_index 
			# element 가 mid_index 값보다 적으면 end_index = mid_index - 1 
		elif element < some_list[mid_index]: end_index = mid_index - 1 
			# element 가 mid_index 값보다 크면 start_index = mid_index + 1 
		else: 
			start_index = mid_index + 1 
			# 위의 조건에 만족하지 않는 경우(element가 list에 없는 경우) 
	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]))

2. 정렬

• 삽입 정렬(Insertion sort): 앞 부분 인덱스의 값과 비교해서 정렬
• 선택 정렬(Selection sort): 인덱스를 선택해서 뒤 인덱스의 값과 비교하여 정렬

정렬은 알고리즘의 기본임. 퀵 정렬, 버블 정렬, 힙 정렬 등 정렬 알고리즘의 종류 다양함.

3. 알고리즘 평가법

• 알고리즘 평가의 기준: 시간(실행시간), 공간(메모리)

✓ 시간복잡도

• 데이터가 많아질수록 걸리는 시간이 얼마나 급격히 증가하는가
• 시간복잡도가 작을수록 좋은 알고리즘

점근표기법(Big-O Notation)

데이터의 증가량에 따른 알고리즘의 시간복잡도를 표기하는 방법
소요시간의 n의 차수가 큰걸로 표기. 상수값은 버리다. 이 때,n은 인풋값을 의미

• 소요시간 20n+10 → 점근 표기법 O(n)

• 2n²+8n+157→O(n²)(+n2이 n이나 1 같은 값에 비해 훨씬 더 큰 값이므로 나머지 값은 큰 영향을 주지 않는다 생각하여 big-O notation에서는 O(n2)만 표기)
  ex) 5n³+100n²+75→O(n³)

주요 시간복잡도 정리

• O(1)
  인풋의 크기가 소요시간에 영향이 없다는 의미 (반복문이 없으면 대체로 O(1))

• O(n)
  반복문이 있고, 반복되는 횟수가 인풋의 크기와 비례하는 일반적인 경우

• O(n2)
  반복문 안에 반복문이 중첩되고, 두 반복문이 다 인풋의 크기에 비례하는 일반적인 경우

• O(n3)
  위와 비슷하게 반복문이 3번 중첩되는 일반적인 경우

• O(lg n)
  i가 2배,1/2씩 증가

# O(lg n) 함수
    # 2의 거듭제곱을 출력하는 함수
    # (이번에는 인풋이 리스트가 아니라 그냥 정수입니다)
    def print_powers_of_two(n):
        i = 1
        while i < n:
            print(i)
            i = i * 2

• O(n lg n)
  O(n)과 O(lg n)이 중첩된 경우
  (1) case1

#for문 안에 while문
    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

    (2) case2

    #while문 안에 for문
    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

✓ 공간 복잡도(Space Complexicy)

인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간, Big-O표기로 나타냄.

• O(1)
• O(n)

    def get_every_other(my_list):
    	every_other = my_list[::2]  #n/2만큼의 공간을 차지함 -> O(n/2)는 O(n)으로 표기
    	return every_other

• O(n²)

    def largest_product(my_list):
        products = []
        for a in my_list:
            for b in my_list:
                products.append(a * b) #값은 두번씩 곱하므로 n²만큼의 공간을 차지
        
        return max(products)

등등

4. 유용한 파이썬 기능 정리

∙ type() 파라미터의 데이터타입 리턴: O(1)

∙ max(), min() 파라미터의 최댓값,최솟값 리턴: O(n)

∙ str() 숫자를 문자열로 변환: O(d), O(log n)

-d는 숫자의 자릿수 의미

• 10진수의 자릿수가 몇 개인지 따져보면

O(log10n)(정수n의 자릿수 표현)

∙ append: O(1)

insert, del, index, reverse: O(n)

∙ sort, sorted: log(n lg n)

-sort는 리스트자체를 정렬, sorted는 정렬된 새로운 리스트 리턴

∙ slicing: O(b-a) (슬라이싱 범위가 [a:b]일때)

∙ len: O(1)