좋은 알고리즘이란?알고리즘 평가법탐색 알고리즘 평가하기

Q

Binary_Search 가왜 big of lgn 인지 다시한번 설명해 주세요.

조회 990

2019년 5월 13일

댓글 1

시간순
2020년 3월 7일
https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf 영어긴 한데 여기 그림으로 설명이 되어 있네요. 간단히 설명하자면 Binary_Search는 ㅊㅗㅣㄷㅐ (2의 k 제곱) = (탐색 리스트 길이 n) 이 만족할떄까지 탐색하니까 log2 n = k 즉 lg n 이 되는 겁니다,
A
1개의 답변이 있어요
커뮤니티 파트너 채택
2019년 5월 13일

댓글 2

시간순
2019년 10월 31일
탐색범위가 반으로 주는게 log2(n)번 실행된다는데 이게 약속인건가요 ???
2019년 11월 7일
실행되는 횟수를 x라고 할 때, 매 실행마다 절반씩 탐색범위가 줄어드니 2^x = n 이 됩니다! 양쪽에 lg를 취해주면 우리가 원하는 탐색 횟수인 x = lg n이 됩니다!

(주) 코드잇

대표강영훈, 이윤수

개인정보보호책임자강영훈

이메일support@codeit.kr

사업자 번호313-86-00797

통신판매업제 2019-서울중구-1034 호

주소서울특별시 중구 청계천로 100 시그니쳐타워 동관 10층 코드잇

전화02-2289-1998