big O = 단계수 계산
빅오는 시간단위가 아닌 알고리즘에 필요한 단계수만을 고려함으로서 일관성을 유지한다.
O(1) (차수 1): 데이터 크기에 상관없이 알고리즘에 필요한 단계수가 일정하다는 의미.
O(N) : 배열 내에 N개의 원소가 있을때 알고리즘을 끝내는데 N개의 단계가 필요
빅오의 수학적 설명
빅오=함수 증가률의 상한값.= 함수 g(x)가 함수 f(x)보다 빠를수 없을때 g는 O(f)에 속한다.
빅오 표기법은 알고리즘에 얼마나 많은 단계가 필요한지 알고리즘이 처리할 데이터 원소 수에 따라 설명한다. 즉 빅오는 데이터가 증가할수록 단계수는 어떻게 변하는가에 대한 답을 한다.
O(N)은 대각선의 우상향 그래프를 그리므로 선형시간이라고 불리고 O(1)은 수평선을 그리므로 상수시간이라고 불린다.
상수시간은 데이터가 아무리 늘어나도 단계수는 상수로 유지됨. O(1)은 데이터가 아무리 커지더라도 단계수가 변하지 않은 모든 알고리즘을 표현하는 방식으로 실제 단계는 1이아니더라도 표현은 O(1)로 둔다.
변화가 생기는 일정량의 데이터는 항상 있을 것이기에 전반적으로 빅오의 차수가 낮을 수록 더욱 효율적인 알고리즘이다.(ex. 백만 단계가 걸리는 O(1)이라도 데이터가 증가할 수록 O(N)이 O(1)보다 덜효율적인 어느 지점에 반드시 다다르게되고, 그 지점부터 데이터양이 무한대로 갈때까지 계속 O(N) 보다 O(1)이 더 효율적
정렬알고리즘 : 컴퓨터 과학 분야에서 폭넓게 연구된 주제이며, 정렬되지 않은 배열이 주어졌을때, 어떻게 오름차순으로 정렬할 수 있을까? 에 대한 해결책이다.