피보나치 수열 에서 O(1) 보다 어떻게 O(log n)이 더 빠를 수가 있죠?
겨레
2023.04.01
질문 내용 :
중학생이긴 하지만 로그에 대한 기본지식은 있습니다. 그런데 어떻게 피보나치 수열 시간복잡도에서 o(log n)이 더 효율적일수가 있죠?
o(1)은 숫자가 아무리 커도 연산하는 속도가 같기 때문에 o(1)이 더 효율적 아닌가요?
-
갤2
피보나치 수열에서 알고싶은 몇번째 숫자가 작아서 그런거 아닌가요? 시간복잡도는 비례관계를 나타내는거여서 큰수에서 작용되는걸로 알아요 예를 들면 0(1)은 3000 이고 O(log n)은 2log n 일 경우가 있다는거죠
-
희미해
.. O(1) 가 더 빠른거 아녔음..? 쩝.. 몰랐네..