[데이터구조]Big O

알고리즘 스피드 표현법

완료까지 걸리는 절차의 수 (STEPS)

선형 검색 알고리즘의 경우 N개의 숫자들을 N번 검색합니다

그래서 선형 검색 알고리즘은 N steps이 요구된다고 할 수 있습니다.

그리하여 선형검색은 O(N)을 갖는다고 합니다.이러한 것을 Big O라고 합니다.

Big O를 이해한다면, 알고리즘 분석을 빠르게 할 수 있고, 언제 무엇을 쓸지 빠르게 파악이 가능합니다.

 

Big O는 큰 원리에만 관심이 있다.

Big O는 상수에는 신경을 쓰지 않는다는 점!!.

O(200) x->O(1)이다.

O(2N) x->O(N)이다

for(int i=0;i <N;i++){

    for(int j=0;j <N;j++){
               System.out.print(i*j);

}

}

이경우는 N이 2일 경우 2번 2번 반복하여 4번이 나오고 3일 경우 3번 3번 반복하여 9가 나옵니다.

그리하여 이 알고리즘은 O(N의 제곱)이 나옵니다.

그리고 이진 탐색의 경우에는 계속하여 2로 나누어 실행하므로  O(log n)이 나옵니다.

BigO를 통해서 알고리즘의 시간 복잡도를 인풋과 연관하여 빠르게 알아낼 수 있습니다. 

 

 

 

출처:https://www.youtube.com/channel/UCUpJs89fSBXNolQGOYKn0YQ