빅오(Big-O)표기법.md

빅오(Big-O)란?

• 알고리즘의 성능을 수학적으로 설명해주는 표기법
• 알고리즘의 시간과 공간 복잡도를 표현할 수 있음.
• 빅오 표기법은 알고리즘의 실제 러닝타임을 표시한다기 보다, 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표이다. 따라서 상수와 같은 숫자들은 모두 1이 된다.

O(1) 알고리즘

• 입력 데이터 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 의미. 크기와 상관없이 언제나 일정한 속도로 결과를 반환해주는 경우이다.
• 이런 경우 해당 알고리즘을 "O(1)의 시간복잡도를 가진다" 라고 표현한다.
• 그래프로 표현하면, 가로축이 데이터의 크기이고 세로축을 처리 시간이라고 할 때 데이터가 증가함에 따라 성능에 변함이 없다.

O(n) 알고리즘

• 입력 데이터 크기에 비례해서 처리 시간이 걸리는 알고리즘을 표현하는 것.
• O(n) 그래프는, 가로축 데이터가 증가함에 따라 비례해서 세로축 처리 시간도 같이 증가하게 된다. 언제나 데이터와 시간이 같은 비율로 증가하기 때문에 그래프는 직선으로 표현이 된다.

O(n^2) 알고리즘 (오 n스퀘어)

• 입력받은 데이터 n개에서 루프를 돌리고 그 안에서 또 돌리는 경우.
• n개의 데이터를 받으면, 첫번째 루프에서 n번 돌면서 각각에 element에서 n번씩 또 돌게 되니까 -> 처리 횟수가 n를 가로, 세로 길이로 가지는 면적만큼 되는 것이다. (구구단 예시처럼..?)
• 그러면, n이 하나 늘어날 때마다 가로, 세로 줄이 추가되는 것이니까 데이터가 커지면 커질수록 처리 시간의 부담도 커지게 된다.
• O(n^2)를 그래프로 표현하면, 가로축 데이터가 증가함에 따라 세로축 처리 시간이 -> 처음에는 조금씩 증가하다가 나중에는 수직 상승하게 된다.

O(nm) 알고리즘

• 코드가 n스퀘어와 비슷하나, n를 2번 돌리는 게 아니라 다른 m를 n만큼 돌리는 경우이다.
• n이 엄청 크고 m이 아주 작을 수도 있기에 변수가 다르다면, 빅오 표기법에도 반드시 다르게 표시해줘야 한다.
• nm도 n스퀘어와 마찬가지로 그래프를 표현했을 때, 데이터가 증가할수록 그래프가 점점 수직에 가까운 모양이 된다.

O(n^3) 알고리즘

• n의 제곱에서 n를 한 번 더 돌리면 n의 세제곱이 된다. O(n)일 때는 직선이었고 / n의 제곱은 면적으로 표현했다. / n의 세제곱은 n의 제곱을 n만큼 더 돌리니까 큐빅의 형태로 표현할 수 있다.
• 그래프로 표현했을 때, n제곱과 비슷한 양상을 보이지만 데이터가 늘어날 때 마다 더 급격하게 처리시간이 늘어나게 된다.

O(2의 n승) 알고리즘

• 피보나치 수열이란, 1부터 시작해서 한 면을 기준으로 정사각형을 만드는 것. 2개가 붙어 직사각형이 되면 큰 면이 2가 되고 그 면을 기준을 2x2 정사각형을 하나 더 붙여주는 것. 그 다음에는 한 면이 3이 되는 정사각형을 만들어 준다. 이렇게 계속 진행하면 피보나치의 나선형이 그려진다.
• 수학적으로 접근해보면, 피보나치 수열은 1부터 시작해서 1의 다른 한 면이 1를 더 써주고, 앞의 1 2개를 더해서 2를 써주고, 1과 2를 더해서 3를 써주고, 2와 3를 더해서 5를 써주고, 3과 5를 더해서 8를 써주는 과정이다. 그래서 매번 함수가 호출될 때마다 전 숫자, 전전 숫자에 대해 함수를 호출한다. 이걸 트리의 높이만큼 반복하는 것이다.
• 그래프로 보면, n의 제곱이나 n의 세제곱 보다도 데이터의 증가에 따라 처리시간이 급격하게 늘어나는 것을 확인할 수 있다.
• O(m의 n승) 알고리즘도 있다.

O(log n) 알고리즘

• log n의 대표적인 알고리즘은 바로 "이진 검색"이다. 1부터 어센딩(오름차순)으로 정렬된 배열(array)안에서 6를 찾는다고 할 때, 이진 검색을 한다면 우선 가운데 값을 찾아서 찾으려는 key 값과 비교한다.
  key 값이 더 크다면 -> 가운데 기준 오른쪽에 값이 있다는 뜻이니까 앞의 있는 데이터들은 안봐도 된다. 그 다음, 뒤쪽에 있는 데이터 중에서 다시 중간 값을 찾아서 key 값과 비교한다. 이번엔 key 값이 더 작으니까 뒤쪽 데이터들을 무시하고 6이라는 값을 찾을 수 있게 된다.
• 이렇게 한 번 처리가 진행될 때 마다 검색해야하는 데이터의 양이 절반씩 뚝 떨어지는 알고리즘을 의미한다.
• 그래프로 표현했을 때, O(log n)이 O(n) 보다도 훨씬 처리시간이 적게 든다.

O(sqrt(n)) 알고리즘 (스퀘어 루트n)

• square root, 제곱근이란.. ex) 100의 제곱근은 10이 된다. 100이 10을 2번 곱한 값이기 때문이다. 9의 제곱근은 3이다. 즉, 제곱해서 그 수가 되는 수를 의미한다.
• 예를 들어 n = 4라면 n을 정사각형에 채워서 맨 위의 한 줄이 제곱근이 된다. sqrt(n) = 2 이렇게 된다.
  n = 9이라면 마찬가지로 n을 정사각형에 채우고 맨 위의 한 줄이 제곱근이 된다. sqrt(n) = 3 이렇게 된다. 이런식으로 n를 받고 정사각형에 채운 다음, 맨 위에 한 줄만 돌리는 알고리즘을 O(sqrt(n))이라고 한다.

관련 자료

https://www.youtube.com/watch?v=6Iq5iMCVsXA&t=172s
https://hibiskim.tistory.com/27