시간 복잡도 계산

https://devraphy.tistory.com/284

시간복잡도 완전정복(1)

시간 복잡도를 코딩 테스트에 활용하는 방법

이제 시간 복잡도를 표현하는 방법이 빅오 표기법이라는 건 알았습니다. 그럼 빅오 표기법을 어떻게 활용하면 좋을까요? 코딩 테스트 문제에는 제한 시간이 있으므로 문제를 분석한 후에 빅오 표기법을 활용해서 해당 알고리즘을 적용했을 때 제한 시간 내에 출력값이 나올 수 있을지 확인해볼 수 있습니다. 그러면 문제 조건에 맞지 않는 알고리즘을 적용하느라 낭비하는 시간을 줄일 수 있습니다. 보통은 다음을 기준으로 알고리즘을 선택합니다.

 

“컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억 번이다.”

 

코딩 테스트의 문제는 출제자가 의도한 로직을 구현했다면 대부분의 코드를 정답 처리할 수 있도록 채점 시간을 충분히 여유있게 지정합니다. 따라서 연산 횟수는 1,000~3,000만 정도로 고려해서 시간 복잡도를 생각하면 됩니다. 예를 들어 제한 시간이 1초인 문제는 연산 횟수가 3,000만이 넘는 알고리즘은 사용하면 안 됩니다. 제한 시간이 1초인 문제에 각 시간 복잡도별로 허용할 수 있는 최대 연산 횟수는 다음과 같이 생각하면 됩니다.

언어별로 성능은 다를 수 있으나 특정 언어가 유리하거나 불리하면 안 되겠죠? 그래서 언어에 따른 성능 차이는 고려하지 않아도 됩니다.

 

 

 

이렇게 하나하나 짚어가며 찾는 방식은 시간 복잡도가 O(N)입니다. O(N)이 허용하는 연산 횟수는 1,000만이므로 데이터의 개수가 1,000만 개 이하면 이 알고리즘은 사용해도 됩니다. 바로 이렇게 시간 복잡도를 활용하여 불필요한 알고리즘을 제외하면 됩니다.

 

 

[참고]

https://wikidocs.net/222560