sia.log
로그인
sia.log
로그인
3장 빅 오 표기법
sia
·
2022년 10월 19일
팔로우
0
누구나 자료구조와 알고리즘
누자알
로가리즘
빅 오 표기법
0
누구나 자료구조와 알고리즘
목록 보기
3/3
알고리즘의 효율성을 결정하는 주 요인은 알고리즘 수행에 필요한 단계 수
배열에 N개의 원소가 있을 때 선형 검색에 N단계가 필요하다고 표현하면…?
빅 오 표기법
1. 빅 오: 원소가 N개일 때 몇 단계가 필요할까?
O(N)
“빅 오 엔”이라고 발음한다.
보통 “빅”을 생략하고 “오 엔”이라고 부름.
알고리즘에 N단계가 필요하다는 뜻
O(1)
1장에서 배열 읽기에 필요한 단계 수는 “배열의 크기와 상관없이” 딱 한 단계.
이때의 표기를 O(1)이라고 한다.
즉 배열에 원소가 몇 개든 한 단계만 필요할 때.
O(1)의 시간 복잡도를 갖는 알고리즘을 가장 빠른 알고리즘 유형으로 분류한다.
상수 시간(constant time)을 갖는 알고리즘이라고도 표현한다.
2. 빅 오의 본질
빅 오가 진정으로 의미하는 것: 데이터가
늘어날 때
알고리즘의 성능이 어떻게 바뀌는지
즉 O(1)과 O(3)은 같다.
별도로 명시하지 않는 한 빅 오 표기법은 일반적으로 최악의 시나리오를 의미한다.
“비관적인” 접근
3. 세 번째 유형의 알고리즘
O(log N): 이진 검색의 시간 복잡도
로그 시간(log time)의 시간 복잡도
로가리즘?
4. 로가리즘
log는 logarithm의 줄임말이다.?
헉
진짜네
Logarithm - Wikipedia
5. O(logN) 해석
컴퓨터과학에서 O(logN)은 사실 밑이 2인 이진로그이다.
O(logN)은 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계수가 걸린다는 뜻이다.
sia
포스트 중 틀린 부분이 있다면 댓글로 지적해 주시면 감사하겠습니다.
팔로우
이전 포스트
2장 알고리즘이 중요한 까닭
0개의 댓글
댓글 작성