시간복잡도에서 생략되는 상수 문제의 경우, 상수가 매우 크면 빠른 시간복잡도를 갖는 코드의 실행 시간도 길어질 수 있고, 반대로 상수가 매우 작아서 느린 시간복잡도를 갖는 코드의 실행 시간이 짧아질 수도 있습니다. 다만 대부분의 문제에서는 의도한 시간복잡도를 갖는 코드는 지나치게 비효율적이지 않는 이상 통과한다고 보시면 됩니다. (사실 위에 나온 예시의 경우, C 계열의 언어라면 1초에 3.2억은 충분히 실행됩니다.)

답변남겨주셔서 감사합니다. 1억번의 연산이 1초라고 가정했을 때

위의 코드는 O(N^2)으로만 봤을 땐 시간초과가 아니지만 실제적으론 시간초과로 판단하는게 맞나요?

1억 번의 연산을 실행하는 데 1초가 걸린다고 가정하는 게 지금은 그다지 정확하지 않습니다.

그래서 저 정도면 그냥 '실행될 수도 있고 시간 초과가 발생할 수도 있다' 정도로 판단하면 되는데, 웬만하면 1초 안에 돕니다. 현재 BOJ에서 C나 C++로 제출하면 가장 간단한 연산 기준으로 1초에 10억 번 정도 실행되는 것 같습니다.

제가 질문드리고 싶었던 요지는

시간복잡도 계산상으로는 제한 시간 내에 실행될 것으로 예측했지만

사실은 추가적인 상수시간에 의해서 제한 시간 내에 실행되지 못할 경우가 존재할 수 있다고 볼 수 있는지에 대한 질문이었습니다 ㅜ

물론 상수 때문에 시간 초과가 발생하는 것도 가능합니다.

감사합니다. 시간복잡도만 생각해선 안되겠군요