빅오 란?

알고리즘 스피드는 완료까지 걸리는 절차의 수 로 결정됨.
예를 들어 선형검색의 경우에는
하나,하나씩 검색하기 때문에 데이터가 10개 라면, 아이템을 찾기까지 10개의 스텝이 필요하다.
input size가 N이라면 N스텝이 요구된다고 할 수 있다. -> 선형검색의 시간 복잡도는 O(N)임.

Big O를 사용하면, 시간 복잡도를 빠르게 설명할 수 있다.

O(1) , 상수 시간

인풋이 100개라도 끝내는건 한번이면 충분하다
이 경우, 인풋이 얼마나 크든 동일한 수의 스텝이 필요하다.
이 함수의 시간 복잡도는 constant time(상수 시간)임.
N이 얼마나 크던 상관 없이 끝내는데 동일한 스템이 필요하다

요걸 읽는 방법은 O(1)

이번에 두개의 출력을 해보쟈

그러면 끝내기 위해 2개의 스텝이 필요하다.
따라서 시간복잡도는 O(2)?? 아님!!!
여전히 동일하게 O(1)로 표현
Big O는 함수의 디테일엔 관심이 없기 때문!!

Big O는 러프하게, 어떻게 이 함수가 작동하는지 인풋사이즈에 따라! 표현

따라서 위 함수가 프린트를 2번 하더라도 여전히 O(1)로 표현한다.
Big O는 상수(constant)에 신경을 쓰지 않는다.
예를 들어, 항상 200개의 스텝이 필요한 함수가 있다면, 인풋 사이즈와 관계 없이
이 함수의 시간 복잡도는 O(1)이다.
여전히 constant time(일정한 시간/ 상수)이니까!

constatnt time 알고리즘은 인풋 사이즈와 관계없이, 스텝이 정해진 알고림즘임.

O(N), 선형 검색

각아이템을 다 프린트 하는 함수.

배열 사이즈가 10이라면 10번 프린트를 한다.
만약 배열 100개 라면, 100개 스텝으로 이어진다.
선형 검색이랑 비슷하다. 배열의 각각 아이템을 위해 모두 작업을 해야한다.
배열이 커지면, 필요 스텝도 커질것.
이를 빅오로 표현하면, O(N).
그리고 이전처럼, 상수는 관계없음

하지만 O(2N)에서 2는 상수이므로 버려버림 -> O(N)으로 표현
O(2N) 이든, O(N)이든, 인풋이 증가하면, 스텝도 선형적으로 증가한다는 사실자체는 변하지 않기 때문!

O(N)혹은 선형 시간복잡도를 그래프로 표현한 그림.

O(N^2) , 2차 시간

2차 시간은 중첩 반복이 있을 때 발생

배열의 각 아이템에 대해 루프를 반복하여 실행.
따라서 시간 복잡도는 인풋의 n^2인것.

인풋이 10개라면, 완성하는데 100번의 스텝이 필요한 것.
왜냐면 루프안의 루프에서 함수를 실행하기 때문!

따라서 2차 시간 보단 선형 시간 복잡도가 더 효율적인것으로 선호된다.

O(log N), 로그시간

이건 이진검색 알고리즘 설명할 때 쓰는거다.
이진검색에선, 인풋 사이즈가 더블이 되어도, 스텝은 딱 +1밖에 증가를 안했다.
왜냐면 이진검색에서는 각 프로세스의 스텝을 절반으로 나눠서 진행하기 때문임.->요걸 표현하면 O(log N)이 됨.
로그는 지수의 정 반대이다.
우리가 찾는 것은 몇번을 나눠야 , 예를 들어 32를 2로 몇 번을 나눠야 1이 나올까 임.
이진검색에서는 매번 스탭을 진행할 때 마다 인풋을 일단 반으로 나누고 시작함.
그렇기 때문에 인풋이 2배로 커져도, 검색을 하기 위한 스텝은 +1만 증가하는것.
왜냐면 한번만 더 나누면 되는것이기 때문.
빅오 노테이션에서는 base를 쓰지 않음!

빅오의 특성상 로그의 밑 숫자는 사라진다.

선형 시간보다는 빠르고 상수시간보다는 느리다.

하지만 이진검색은 정렬되지 않은 배열엔 사용할 수 없다.