시간복잡도 계산할 때 상수 무시

시간복잡도와 관련해 질문이 생겨 작성합니다.

코테를 풀며 시간 복잡도를 계산할 때도 상수를 무시해야하나요? 아니면 상수를 고려해서 연산을 몇 번하는지를 기준으로 코드를 짜면 될까요?

예를 들어 N이 2,000이고 N앞의 상수가 10인 문제에서 O(n^2)의 시간복잡도를 가진 코드를 작성했다고 가정해보겠습니다. 그러면 실제 연산은 10 * (2,000^2)번을 하게 되는데, 파이썬의 경우 제한시간이 1초일 때 N이 2,000을 넘으면 시간초과가 나는 것으로 알고있습니다.

즉 상수값때문에 실제 연산을 10배를 더 하는데, 위 경우에는 빅오 노테이션으로 계산해야할까요 아니면 상수값도 고려해서 연산 수를 초점으로 계산해야할까요? 빅오 노테이션으로 계산해도 시간초과가 발생하지않나요?

안녕하세요, 인프런 AI 인턴이에요. 시간 복잡도를 계산할 때에는 일반적으로 빅오 표기법을 사용하여 상수 항을 무시합니다. 이는 알고리즘의 성능을 대략적으로 파악하고 비교하기 위한 것입니다.

따라서, 예를 들어 N이 2,000이고 N앞의 상수가 10인 경우에 O(n^2)의 시간복잡도를 가진 코드를 작성했다면, 실제로 10 * (2,000^2)번의 연산을 하게 될 것입니다. 이 때 체감상으로는 상수가 있더라도 상수값이 큰 영향을 미치지 않기 때문에, 해당 알고리즘의 시간 복잡도는 여전히 O(n^2)로 간주됩니다.

하지만 상황에 따라 상수 값이 큰 영향을 미칠 수도 있습니다. 예를 들어 제한 시간이 매우 촉박하거나 연산 횟수가 매우 큰 경우에는 실제 연산 횟수에 대해 상수를 고려하는 것이 필요할 수 있습니다. 이런 경우에는 빅오 표기법으로 계산해도 시간 초과가 발생할 수 있으므로, 상수값도 고려해서 연산 횟수를 초점으로 계산하는 것이 좋습니다.

하지만 일반적으로 대부분의 경우에는 상수는 무시하고 빅오 표기법으로 시간 복잡도를 계산하는 것이 일반적이며, 알고리즘 성능의 대략적인 파악에도 충분합니다. 따라서 상황에 따라 상수를 고려할지 여부를 판단하는 것은 개발자의 판단에 달려 있습니다.

원하는 결과를 얻기 위해 알고리즘을 분석할 때에는 실제 연산 횟수를 고려할 필요가 있을 때에 한해 상수 값을 고려하여 계산하시면 됩니다. 그러나 대부분의 경우 상대적인 알고리즘 성능을 비교할 때에는 상수는 무시하는 것이 일반적입니다. 이에 따라 알고리즘을 평가하고 선택할 때 빅오 표기법을 사용하여 비교하는 것이 일반적이고 보편적인 방법입니다.

더 궁금한 사항이 있으시면 언제든지 물어보세요. 즐거운 프로그래밍 되세요!

인프런 커뮤니티 질문&답변