<![CDATA[
<div class="figure-img" data-ke-type="image" data-ke-style="alignCenter" data-ke-mobilestyle="widthOrigin"><img src="https://t1.daumcdn.net/cafeattach/1Gq2f/f8cb785307075443745dbda98c6685052724d82c" class="txc-image" data-img-src="https://t1.daumcdn.net/cafeattach/1Gq2f/f8cb785307075443745dbda98c6685052724d82c" data-origin-width="3999" data-origin-height="601"></div><p><span data-ke-size="size20">이진탐색의 최악 수행시간이 O(n)이라서, 당연히 이진탐색의 반복, 재귀알고리즘도 최악시간이 O(n)인 줄 알았는데,</span></p><p><span data-ke-size="size20">둘 다 O(log n)인건가요??</span></p>
<!-- -->
]]>
카페 게시글
자료구조론
이진탐색-재귀, 반복 수행시간
세제
추천 0
조회 107
21.10.15 00:19
댓글 2
다음검색
첫댓글 이진탐색의 최악 수행시간은 O(n)이 아니고, O(log n) 입니다.
array에서 이진탐색하는 경우엔 최악의 경우 lg N입니다. 이진탐색트리에서 탐색하는 경우엔 최악의 경우 N이 됩니다