밑변환 공식에 의해 밑이 서로 다른 로그는 상수배 차이나므로 big O 표기법에서는 어떤 밑을 쓰든 상관 없습니다.

뿐만 아니라 알고리즘에서 그냥 로그를 쓰면 거의 밑을 2로 암묵적으로 쓰는 것으로 생각해도 됩니다.

그러니까, 시간 복잡도라는 개념 자체가 점근 표기법을 사용하는 것이기 때문에 수학적인 정의상 밑이 얼마든 상관이 없다는 뜻입니다. 다시 강조드리자면, 그 알고리즘을 구현한 코드의 시간이 실제로 얼마가 걸리는지는 시간 복잡도만으로는 정확히 알 수 없고, 아주 대략적으로만 추측할 수 있을 뿐입니다.

그럼 대략적인 추측에서 더 확실하게 확인하려면 어떻게 해야하나요?

다른 글에서 그건 어렵다고 말씀드렸습니다. 문제를 풀면서 어떤 코드가 얼마나 걸리는지 감으로 익히시는 수밖에 없습니다.이론적인 부분을 공부하시려면 컴퓨터 구조, 컴파일러 같은 걸 공부해보시면 도움은 됩니다.

합이 0인 네 정수

https://www.acmicpc.net/proble...

문제의 경우에

16000개의 숫자를 정렬해서 문제를 푸는 분들이 많은데,

그럼 nlogn 으로 계산했을 떄는 아슬아슬하게 통과하지만

nlog(2)n 으로 햇을 때는 시간초과가 날것으로 보이거든요

흠

왜 계속 그 값 자체에 의미를 두시는지 모르겠습니다. 일단 수학적으로, 점근 표기법을 사용한 O(nlogn)은 O(nlog2n)과 완전히 같습니다. 다시 말씀드리지만 점근 표기법으로 나타낸 값 자체에는 큰 의미가 없습니다. 실제로 그걸 구현한 코드가 얼마나 무거운 연산을 몇 번 하느냐에 달린 거죠. 그 '몇 번'이라는 값은 nlogn의 1/10000일 수도 있고, 10000배일 수도 있지만, 둘 다 점근적으로는 완전히 같습니다. 똑같아요.

비유를 한 번 해볼까요. 질문자님이 어떤 집에서 청소를 하는데, 작은 방을 청소하는 작업이 있고 큰 방을 청소하는 작업이 있습니다. 큰 방을 청소하는 건 작은 방을 청소하는 시간의 10배가 걸린다고 해봅시다. 각각의 작업을 n번 하는 건 둘 다 O(n) 시간이 걸립니다.실제로는 시간 차이가 10배나 나는데, 점근 표기법으로는 똑같이 써도 된다는 뜻입니다. 마음대로 의미를 붙여서, 큰 방 청소는 작은 방 청소의 10배가 걸리니까 큰 방 청소를 n번 하는 건 O(10n)이라고 써도 됩니다. 아무 의미가 없습니다.

중요한 건 여기서는 큰 방 청소가 작은 방 청소의 10배 걸린다는 걸 알고 있지만, 어떤 코드에서 계산한 단위 연산이 실제로 소모하는 시간이 얼마인지는 정확히 모른다는 것입니다. 이건 시간 복잡도와는 완전히 별개입니다. 다만 이 값이 대부분의 알고리즘에서 터무니없이 크거나 작지는 않으니까 대략적인 선을 정해놓고 그 정도로 생각하면 얼추 비슷하다고 하는 것입니다. 실제로 어떤 코드가 얼마나 걸릴지는 알고리즘 자체와는 별개로, 컴파일러와 컴퓨터 구조 및 운영체제에 대한 깊은 이해를 바탕으로 계산을 해야만 정밀한 예측이 가능한 것입니다.

그렇군요 감사합니당

결국 해보는건

복잡도로 어림잡아놓고

시행착오를 통해서 감을 익히는게 맞군요