1억번 → 1초

시간 복잡도 순서

0 < (1) < O(logN) < O(N) < O(nlogN) < O(N^2) < O(N^3) < O(2^N)

N : 500 일 경우

O(N^3)까지 가능

N : 2000

O(N^2)

N : 100,000

O(nlogN)

N : 10,000,000

O(N)

시간이 늘어나는 이유

• ᆞ시간 복잡도가 프로그램의 실제 수행 속도를 반영하지 못하는 경우: O 표기법으로 시간 복잡도를 표현할 때는 상수나 최고차항 이외의 항들을 모두 지워 버립니다. 따라서 시간 복잡도 식에 입력의 최대 크기를 대입한 결과는 어디까지나 적당한 예측 값일 뿐입니다. 실제 프로그램이 수행하는 반복문의 수는 이 계산의 다섯 배일 수도 있고, 10분의 1일 수도 있습니다.
• ᆞ반복문의 내부가 복잡한경우: 반복문 내부는 단순하면 단순할수록 좋습니다. 반복문의 내부가 길거나, 시간이 많이 걸리는 연산(실수 연산, 파일 입출력 등)을 많이 사용할 경우에는 이 가정보다 시간이 오래 걸릴 수밖에 없지요. 반대로 반복문의 내부가 아주 단순한 경우에는 이 가정보다 프로그램이 빨리 수행될 겁니다.
• ᆞ메모리 사용 패턴이 복잡한 경우: 현대의 CPU는 메모리에 있는 자료를 직접 접근하는 대신 캐시라고 부르는 작고 빠른 메모리로 옮겨온 뒤 처리합니다. 메모리에서 캐시로 자료를 가져올 때는 인접한 자료들을 함께 가져오기 때문에, 인접한 자료들을 연속해서 사용하는 프로그램은 메모리에서 매번 자료를 가져올 필요 없이 캐시에 이미 저장된 자료를 사용하게 됩니다. 이런 차이는 시간 복잡도에는 아무 영향을 미치지 않지만 프로그램의 실제 수행 속도는 훨씬 빨라지게 됩니다.
• ᆞ언어와 컴파일러의 차이: 앞의 법칙은 최적화 옵션을 켠 현대 C++ 컴파일러를 기준으로 합니다. 만약 최적화 옵션이 꺼져 있거나, 그보다 느린 언어를 사용한다면 수행 시간이 더 걸릴 수밖에 없습니다.
• ᆞ구형 컴퓨터를 사용하는 경우: 이건 너무나 당연하지요. 위의 법칙은 대략 지 난 4~5년 사이에 출시된 CPU들을 기준으로 합니다.

알고리즘 문제 해결 전략