jng6017   2년 전

보통 문제를 풀때 n^2이니 이런애기를 하는데

시간제한이 1초라고하면 1초에 몇번 연산을 한다고 생각을 해야하나요?

1초에 연산을 10억번 하면 예를 들어 아슬아슬하게 n^2이 10억살짝 안되면 프로그램이 돌아간다는 애기인가요?

yukariko   2년 전

1초에 10억은 한 기능단위가 아니라 연산의 최소단위를 말하기때문에 n^2 같은 시간복잡도 와는 거리가 있습니다.

o(n)으로도 복잡한 연산이 들어가면 1초로 시간초과가 나올수도 있죠.

pl0892029   2년 전

시간복잡도는 문제에 주어지는 비결정변수들과의 증가관계를 나타내기 위해 사용한다고 보시면 됩니다.

O(N)은 N이 증가함에 따라 선형적으로 증가함을 의미하고, O(N^2)은 N의 제곱에 비례하여 증가한다고 보시면 됩니다.

1초에 10억번이라는건 (저같은 경우 1초에 1억번이라 생각합니다만) 본인이 생각한 해당 시간복잡도에 대한 경계값이라 생각하면 됩니다.

N이 10만인데, N^2 은 100억이 되기 때문에 1초 내에 못들어오겠구나! 정도로 참고용으로만 생각하심 됩니다. (이걸 반드시 신뢰할 수 없는 이유는, 일부 문제에서는 불필요한 계산을 커팅하는 개선 방법들이 적용되었을 떄, 시간복잡도는 동일하지만 효율이 뛰어나게 개선되는 경우가 많기 때문에 반드시 그렇다고 생각하시면... 피곤해지십니다. ㅋㅋ)

댓글을 작성하려면 로그인해야 합니다.