f = f(n/2) +1 위 식의 시간복잡도를 구하라는 문제가 있었는데... 나는 O(n) 같거든요.. 근데 답은 O(log n)이래요.. 설명에는 숫자로 어쩌구 저저꾸 하면서 결국 O(log n)이 된다고... 시간복잡도가 O(log n)인 알고리즘의 대표적인게 이진탐색이잖아요.. 원소의 수가 10 이면 연산은 3번 100 이면 7번 정도 10,000 이면 15번 정도? 백만이면 한 30번 정도? 뭐 정확한진 않지만 대충 저정도인데... 아무리 생각해봐도 저 함수는 n이 100 이면 51번..... 백만이면 약 5십만... 해서 시간 복잡도는 n에 정비례하는 O(n)이 맞을것 같은데...
f = f(n/2) +1 위 식의 시간복잡도를 구하라는 문제가 있었는데... 나는 O(n) 같거든요.. 근데 답은 O(log n)이래요.. 설명에는 숫자로 어쩌구 저저꾸 하면서 결국 O(log n)이 된다고... 시간복잡도가 O(log n)인 알고리즘의 대표적인게 이진탐색이잖아요.. 원소의 수가 10 이면 연산은 3번 100 이면 7번 정도 10,000 이면 15번 정도? 백만이면 한 30번 정도? 뭐 정확한진 않지만 대충 저정도인데... 아무리 생각해봐도 저 함수는 n이 100 이면 51번..... 백만이면 약 5십만... 해서 시간 복잡도는 n에 정비례하는 O(n)이 맞을것 같은데...
100번일때 51번 수행되냐.. -_-..
각 잡아라
울학교 자료구조 시험 문제네 -_-;; f가 log n이면 log n = log n/2 + 1 이고 우변이 다시 log n - 1 + 1이 되니까 f = log n 이네효
딱 봐도 lg n인데 -_-
쿼리좀 저렇게 쓰지말자 초보자티나 가독성 좋게
http://cfile6.uf.tistory.com/media/14312B124C468A2A01881B