자바 알고리즘 공부 2일차(2)

홍석진·2021년 9월 6일
0
post-thumbnail

📖빅 O 표기법(big O notatio)

앞에서 예를 들어 설명한 선택정렬! 이차 알고리즘이라고 했었는데, 상수 선형 이차 이러한 알고리즘의 효율을 표기해주는 표기법이 있습니다. 바로 빅O 표기법입니다. 빅O 표기법을 설명해 드리기 전에 점근 표기법이라는 것을 알고 가야합니다. 점근 표기법은 빅오(Big-O), 빅오메가(big-Ω),빅세타(big-Θ)가 있는데 간단하게 설명드리자면 빅오는 상한선, 빅오메가는 하한선, 빅세타는 하한과 상한선 사이쯤 으로 표현한다는 말입니다. 그 중에서 왜 빅O를 사용하는가에 대해서는 빅O는 상한선 이기에 최대시행(worst-case)할 것을 나타내주죠. 빅오메가는 하한선인데 최소시행(best-case)을 나타내 주는데 알고리즘이라는 것은 항상 best-case가 나오지 않기 때문에 하한선은 의미가 없어집니다. 결국 알고리즘에 효율성이라는 것은 worst-case, 최대 시행 횟수만 생각하면 되는 것입니다.

BigO 예시.

  1. O(1) : 스택에서 Push, Pop

  2. O(log n) : 이진트리

  3. O(n) : for 문

  4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)

  5. O(n2): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)

  6. O(2n) : 피보나치 수열

출처: https://noahlogs.tistory.com/27 [인생의 로그캣]에서 더 자세한 내용을 읽어볼 수 있습니다.
위 내용을 이해 하셨으면 빅O의 간편한 방법을 설명해 드리겠습니다. 빅O는 가장 큰 지수만 신경쓰면 되고 155n + 10000라는 알고리즘을 빅O로 표현하면 O(n)입니다. 시간복잡도는 가장 큰 영향을 미치는 것을 따집니다. n을 명령어의 실행이라고 생각하면 되고 (컴퓨터의 하드웨어 또는 프로그래밍 언어에 따라 편차가 크게 달라지기 때문에)"앞의 숫자나 상수 상관없이 지수만 생각하면 된다" 만 기억하면 되기에 쉽게 사용할 수 있을 것 같습니다.
빅오알고리즘쉽게이해하기링크를 읽어보시면 더 이해하는데 도움이 될 겁니다.

이번 정리를 통해서 알고리즘을 살짝 맛봤는데 아직까지는 간단해서 할 만한 것 같습니다. 초반이어서 예제도 쉽고 책 내용도 자세하게 다루는데 예제가 어려워지면 타협을 해야 할 지도..

profile
질문이나 의견이 있으시면 남겨주세요. 서로의 발전이라고 생각합니다.

0개의 댓글