반응형 선형1 O(N) vs O(2N)은 동일한 시간 복잡도를 갖는다. O(N) vs O(2N)은 동일한 시간 복잡도를 갖는다. 결론부터 이야기하자면 O(N)과 O(2N)는 동일하다. O(N)과 O(2N)이 서로 혼동되어 다르다고 생각한다면 '입력 크기에 따라 런타임이 얼마나 빠르게 증가하는가'가 아니라 '작업 횟수'에 초점을 맞추고 있기 때문이다. 시간 복잡도는 수행시간이 아니다. 아래의 그래프를 보면서 확인해 보자 두 경우 모두 'No Of Operations'가 입력 크기에 따라 그래프가 선형적으로 증가하는 것을 볼 수 있다. 실질적으로 O(N)은 O(2N) 보다 실행 시간이 짧지만 이는 중요하지 않다. N 값이 증가하면 O(N)이 성장을 지배하게 되고 계수 2는 중요하지 않게 된다. 따라서 N의 값이 매우 커지면 둘의 실행 시간이 동일해질 것이다. 예를 들어보자 T(.. 2023. 12. 5. 이전 1 다음
