똑똑한 프갤행님들 알고리즘 복잡도 질문좀 받아주이소!

[제발제발요(pitsdi)]

binary search 랑 quick sort 복잡도가 책마다 다르게 표기되어 있는데 어느게 맞음?

책1 : binary search : log2n , quicksort : nlog2n

책2 : binary search : logn , quicksort : nlogn

[kukyakya(180.64)]

둘 다 같은 의미임

[제발제발요(pitsdi)]

상수로그는 밑이 10인 로그 아닌가요?? 복잡도 표기할 때는 다르게 표기되는 건가요?

[제발제발요(pitsdi)]

상용로그 말잘못

[kukyakya(180.64)]

big-O notation의 정의가 '충분히 큰 n에 대해 |f(n)| <= M |g(n)|인 M이 존재한다'라는거잖아? 여기서 g(n) = log_2(n)이면 log 밑 변환에 의해서 g(n) = log_2(n) = log(n)/log(2)가 되고

[kukyakya(180.64)]

M|log_2(n)| = (M/log(2)) |log(n)| = M' |log(n)|이 되니까 결국 로그의 밑은 상관이 없어

[kukyakya(180.64)]

O(n)이랑 O(1000*n)이 왜 같은지를 생각해보면 이해가 될거야

[익명(211.109)]

ㄴ이거