목록시간복잡도 (1)

Software Engineering Note

시간 복잡도는 왜 따져봐야 할까?

1. O(N^2), O(N), O(logN)... 자료구조나 알고리즘 시간에 많이 보던 수식입니다. 머릿속에는 이런 형태의 공식으로 박혀있죠. "x 알고리즘 = 복잡도 y" 저도 꽤 오랫동안 그랬던 것 같습니다. 하지만 현업에서도 이걸 잘 따져봐야 하는 일들이 가끔 생깁니다. 예를 들어봅시다. 당신이 만든 프로그램이 2중 for 문으로 구성되어있다고 합시다. 복잡도가 O(N^2) 라고 해보죠. 시간이 너무 오래 걸려서 개선을 하고 싶습니다. 당신은 N을 약 N-3 정도로 줄여서 약간 개선시켜, 다행히 사용 가능한 정도는 되었습니다. 이건 잘 개선되었다고 말할 수 있을까요? 아마 높은 확률로 머지않아 문제가 생길 겁니다. 그런데 새로운 방법을 생각해서 복잡도를 O(N*logN) 정도로 개선을 했다고 합시다..
일하며 개발하며 2020. 3. 18. 21:44
이전 Prev 1 Next 다음