BigO란?

#알고리즘 #코딩 #노마드 코더

본 포스팅은 노마드코더 영상을 정리하며 학습하기 위한 목적을 가지고 있습니다.

---

BigO를 알아보자

작성된 코드는 더 빠르다, 더 느리다는 시간으로 표현하지 않는다.

왜 그럴까?

속도는 하드웨어가 결정하기 때문에 시간으로 표현하지 않고 알고리즘 속도는 '완료까지 걸리는 절차의 수'로 결정한다.

예를 들어, 딱 5번의 스탭이 10개스탭보다 훌륭한 알고리즘인 것이다.

선형 검색은 한개씩 한개씩 검색해 데이터가 10개면 10개 스텝이 필요하다. 선형 알고리즘은 input 사이즈가 n이라면 n스텝을 요구하게 된다.

따라서 선형 검색의 시간 복잡도는 O(N)이고 그래프로 표현하면 다음과 같다.

O(N)

이렇게 BigO는 시간복잡도를 빠르게 설명할 수 있다.

이것을 이해하면 알고리즘 분석을 빠르게하고 언제, 무엇을 쓸지 빠르게 가능하게 된다. 

코드 평가할 때에도 유용하며 미래에 어떻게 작동하는지 알 수 있다.

다음으로 알아볼 시간 복잡도는 O(1)이다.

이 시간복잡도는 상수 시간으로 N이 얼마나 커지던지 동일한 숫자의 스텝이 필요하다.

예를 들어 다음과 같은 코드를 들 수 있다.

function bigO(int i){
	System.out.println(i);
}

 

BigO는 함수의 디테일엔 관심없이 러프하게 책정된다. 다음 코드를 보자.

function bigO(int i){
	System.out.println(i);
	System.out.println(i);
}

큰 원리에만 관심있지 이렇게 print를 두번한다고 늘어나지 않는다.

아래의 코드처럼 N이 커질때 N만큼 커지는 시간복잡도가 O(N)이 되는 것이다.

function bigO(int i){
  for(int j = 0; j < 10; j++){
    System.out.println(i);
    System.out.println(j);
  }
}

그럼 이중 for문의 시간복잡도는 무엇일까?

function bigO(){
  for(int i = 0; i < 10; i++){
    for(int j = 0; j < 10; j++){
    	System.out.println(j);
    }  
  }
}

답은 바로 O(n^2)이다.

 

시간복잡도에는 로그도 있다.

로그 시간은 이진 검색 알고리즘을 예로 들 수 있으며 2^5 = 32를 생각해보면

n = log2 32 몇번을 2로 나눠야 1이 나올까 판단하면 된다.

O(log n)은 선형보다 빠르며, 상수보다 느린데 이 시간복잡도는 트레이드오프(상충관계)가 있다. 지난 시간 이진검색에서 배웠으니 모른다면 복습하고 오자.

이미지 출처 : Nomad coders bigO

 

오늘 성장에 도움을 주신 개발자분들 

참고문헌 : 노마드 코더 - https://www.youtube.com/watch?v=BEVnxbxBqi8