배운 내용을 개인적으로 정리하는 블로그입니다. 틀린 내용이 있을 수 있으며 첨언은 언제나 감사합니다 :)
Big-O 표기법
알고리즘이 얼마나 효율적인지 측정하는 함수(알고리즘이 최악의 경우에 걸리는 시간을 표기함)
| O(n) | 내용 |
|---|---|
| O(1) | 데이터량에 상관없이 연산시간 일정 |
| O(n) | 데이터 량 비례해 일정하게 연상시간 증가 |
| ex)순차탐색 | |
| O(log n) | 데이터량에 비해 초반엔 시간이 확 증가하다가, 데이터양이 많아질수록 확 줄어들음 |
| ex)이진탐색 |
계산법
big-O 표기법의 계산법은 의외로 쉬운데, 가장 큰 항만 남겨놓고 앞뒤로 자른다!
필자의 경우 이를 고등학생때 배운 limit로 이해했다(틀렸다면 지적 부탁한다!)
어짜피 무한으로 커지는 경우의 수에서는 고정값인 상수는 의미가 없어지기 때문에 n의 값만 남겨 놓는 것이다.
따라서 단순하게, 변수가 나오는 횟수를 n으로 계산해
세번 나왔다면 3n, 2번이라면 2n 으로 계산하는 것이다.
즉.. 아래의 루틴으로 진행하면 된다는 거시다!
- 변수를 계산 하는 부분을 n으로 잡는다.
- 항이 제일 높은 것만 냅두고 나머진 지운다.
- 그 후 앞의 숫자는 빼고 계산
- 결과값이 나옴.
(반복문 하나의 경우 보통 O(n))
아래의 예를 보고 이해해 보자
대표적인 예 중 하나인 순차탐색을 계산해보면
3n+2 가 되는 것을 알 수 있다.
이를 앞뒤 숫자 다 자르고 n만 남기면... O(n)이 된다.
다른 예시인 버블정렬도 있따!
변수 n을 함수에 넣었을 때, 큰 겉의 for문이 n번째 돌아갈때 안의 for문도 n*n만큼 돌아가게 된다. n²이 된다는 것.
(부가적인 계산 요소가 있지만, 중요한 n만 계산 했을 때는 이렇다.)
JS 태그에 들어있긴 하지만, 프로그래밍 전반적으로 사용되는 표기법인것 같다. 점진 표기법? 이라고 하는 것 같은데 이는 나중에 추가로 알아보면 좋을 듯하다.
개인적인 좁은 식견으로는, 비전공자가 부족한 점을 찾는다면 바로 이런게 아닐까 싶다😂
프로그래밍할 때 직접적으로 꼭 필요한 문법은 아니지만 배워두면 쓸 곳이 있거나 생각을 펼칠때 도와주는 도구들
그러나 찾아보지 않는 이상 접할 일이 적기 때문에 이렇게 알게 될 때마다 적어보고자 한다.
대학생때 이런 지식들을 배울 수 있었다면 얼마나 좋을까 간간히 후회를 해보지만, 이미 지나간 거 어쩌겠슴까 지금부터라도 배워야지!
