빅오 증가: 각 복잡도 클래스가 실제로 치르는 비용

귀하의 데이터

두 알고리즘을 맞대면

상수는 표기법이 버리는 모든 것입니다. 메모리 할당, 캐시 미스, 한 단계 안에서 하는 일. 한쪽에 더 무거운 상수를 주고, 그것이 더는 중요하지 않게 되는 지점을 보세요.

이 페이지는 당신의 반복문을 읽지 않습니다. 소스에서 복잡도를 추측하는 일은 측정의 옷을 입은 짐작입니다. 반복문은 중간에 빠져나올 수 있고, 그 안의 호출 하나가 진짜 비용을 숨길 수 있으며, 재귀는 하는 일대로 읽히는 경우가 드뭅니다. 클래스는 당신이 고르고, 거기서부터의 계산은 정확합니다.

결과

이 페이지가 시작하는 숫자에서 교차점은 439개입니다. 200개짜리 목록에서 '더 좋은 클래스'로 갈아탄 사람은 프로그램을 느리게, 코드를 어렵게 만들었을 뿐입니다. 표기법은 경고하지 않습니다. 표기법이 말하는 것은 결국 어떻게 되느냐이지, 당신에게 무슨 일이 일어나느냐가 아니기 때문입니다.

이 크기에서의 각 클래스

마지막 열이야말로 응시할 값어치가 있습니다. 아무도 머릿속에 담고 다니지 않는 열이기 때문입니다. 선형 작업은 두 배가 됩니다. 이차 작업은 네 배가 됩니다. 지수 작업은 제곱이 됩니다. 이미 1000개가 있는 상태에서 입력을 두 배로 하면 비용은 2의 1000제곱 배, 자릿수가 302개인 수가 됩니다.

계승이 나쁜 방식은 두 배와는 아예 결이 다릅니다. 항목 하나를 더하면 비용이 새 개수만큼 곱해집니다. 즉 스물한 번째 항목은 스무 개짜리 문제 전체의 스물한 배입니다. 그래서 스무 도시의 외판원 문제를 정확히 풀면 2.4 × 100만 × 100만 × 100만 걸음, 초당 10억 번이라도 77년입니다. 같은 스무 도시가 2의 n제곱이라면 1000분의 1초에 끝나는데도요.

같은 이유로, 클래스 사이의 격차는 작은 크기에서는 심심하고 큰 크기에서는 가혹합니다. 10개에서는 n log n과 n 제곱이 세 배 차이라 아무 사용자도 알아채지 못합니다. 1000개에서는 100배, 100만 개에서는 5만 배입니다. 같은 두 알고리즘, 같은 코드, 바뀐 것은 입력뿐입니다.

그러니 복잡도 클래스를 정직하게 읽으면, 그것은 곡선의 모양에 대한 약속이지 속도에 대한 약속이 아닙니다. 입력이 커질 때 비용이 어떻게 반응하는지를 말할 뿐, 오늘 당신의 기계에서 실제 크기로 빠른지에 대해서는 아무 말도 하지 않습니다.