알고리즘

탐색

선형 탐색

순서대로 차례로 탐색하는 방법

이진 탐색

정렬이 되어있는 데이터에서 절반씩 쪼개서 탐색하는 방법

정렬

선택 정렬

순서대로 탐색해서 가장 작은 인덱스와 가장 앞의 인덱스의 자리를 바꾼다.
그 후에 정렬이 완료된 그다음 인덱스 부터 가장 작은 인덱스를 찾으며 반복한다.
즉 가장 작은 값을 찾아서 0번 인덱스와 위치를 바꾸고, 두번째로 작은 값을 찾아서 1번 인덱스와 위치를 바꾸고…. 이 과정을 반복한다.

삽입 정렬

선택 정렬이 각 위치에 어떤 값이 들어갈지 찾는것과 달리 삽입 정렬은 각 값이 어떤 위치에 들어갈지 찾는다.
인덱스를 비교해가면서 해당 인덱스의 값보다 작은 값의 인덱스의 뒤에 끼워넣는다.

알고리즘 평가법

시간 복잡도

시간 복잡도는 데이터가 많아질수록 걸리는 시간이 얼마나 급격하게 증가하는 지를 평가한다.

거듭제곱

2^3 = 2 * 2 * 2 = 8
2^2 = 2 * 2 = 4 = 2^3/2
2^1 = 2 = 2^2/2
2^0 = 1 = 2^1/2
2^-1 = 1/2 = 2^0/2

로그

거듭제곱의 반대개념
loga^b = x -> a^x = b
b를 a로 몇 번 나누어야 1이 되는가
b = 진수, a = 밑수
log2^8 = 3 -> 2^3 = 8
log3^27 = 3 -> 3^3 = 27

밑이 2인 경우에는 이렇게 표기할 수도 있다.
log2^16 = lg 16

1부터 n까지의 합

n * (n + 1) / 2

점근 표기법(Big-O Notation)

n의 영향력이 가장 큰 값에서 숫자를 빼고 표기한다.
20n + 40 -> O(n)
2n^2 + 8n + 157 -> O(n^2)
20lgn + 60 -> O(lg n)

탐색 알고리즘 평가

	선형 탐색	이진 탐색
최고의 경우	O(1)	O(1)
최악의 경우	O(n)	O(lg n)

선형 탐색은 끝 까지 탐색하면 n번 실행한다.
이진 탐색은 탐색범위가 1미만이 될 때까지 실행한다. 한번 실행할 때 마다 탐색 범위가 반으로 줄기 때문에 log2(n)번 실행된다.
이진 탐색이 O(lg n)인 이유

주요 시간 복잡도

• O(1)
  인풋 크기와 상관 없이 실행되는 코드는 O(1)이다.
• O(n)
  반복되는 횟수가 인풋의 크기와 비례하면 O(n)이다.
• O(n^2)
  반복문 안에 반복문이 있고 두 반복문 다 인풋의 크기에 비례하면 O(n^2)이다.
• O(lg n)
  반복문에서 두배씩 증가하거나 반씩 나눌때 O(lg n)이다.
• O(n lg n)
  O(n)과 O(lg n)이 겹쳐진 것이다.
  반복문이 n에 비례하고 반복횟수가 lg n에 비례하거나,
  반복문이 lg n에 비례하고 반복횟수가 n에 비례할 수 있다.

공간 복잡도

인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 나타낸다.

주요 공간 복잡도

• O(1)
  변수가 차지하는 메모리 공간은 인풋과 무관하기 때문에 O(1)이다.
• O(n)
  리스트가 차지하는 메모리 공간.
• 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)
  

  products리스트에 가능한 모든 조합의 곱이 들어간다.