[알고리즘] 0726

Big O 표기법

• O(n) 에서 n은 연산횟수

• 단순탐색 -> O(n)

• 이진탐색 -> O(log n)

• 연산횟수가 어떻게 증가하는지로 측정

• 데이터의 크기가 늘어날 때 알고리즘의 실행 속도가 얼마나 증가할지 할 수 있음.

선택정렬 O(n²)

• 원소 하나당 모든 원소를 비교한다(비교할 원소 수가 줄어들긴 함)

• 빅오표기법은 상수항은 무시한다

• 특정한 원소만 알고싶다면 연결 리스트는 좋지 않다.

• 배열
  읽기: O(1)
  쓰기: O(n)

• 리스트
  읽기: O(n)
  쓰기: O(1)

재귀함수

• 자기 자신을 호출

• 기본단계 -> 함수가 자기 자신을 다시 호출하지 않는 경우

• 재귀단계 -> 함수가 자기 자신을 호출하는 부분

스택

• push -> 가장 위에 새 항목 추가

• pop -> 가장 위의 항목을 떼어내고 읽음

• 호출스택 -> 여러개의 함수를 호출하면서 함수에 사용되는 변수를 저장하는 스택

퀵 정렬

• 분할 정복

1. 기본 단계 해결
2. 문제가 기본 단계가 될때까지 작게 만듬

• 퀵 정렬
  1.기준 원소를 고른다.
  2.배열을 기준 원소보다 작은 원소의 하위배열과 기준 원소보다 큰 원소의 하위배열로 분할한다.
  3.하위 배열에 대해 재귀적으로 퀵정렬을 호출한다.

• 퀵 정렬이 O(n x log n) 인 이유

O(n) -> 분할을 위해 배열을 비교하는 시간
O(log n) -> 호출 스택의 높이

따라서 O(n) x O(log n) = O(n log n)

• 퀵 정렬을 구현하려면 기준 원소를 무작위로 선택해야한다.