편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
200번째 줄: | 200번째 줄: | ||
<math>n=10</math> 정도의 작은 데이터에서는 100배 더 느리다고 해도 불과 0.0001초 정도밖에 차이가 나지 않을 것이다. 데이터의 크기가 적으므로 두 프로그램 모두 매우 빠르기 때문이다! 하지만 <math>n=100,000</math>에서는 100배의 차이는 생각하는 것만큼 매우 크다. <math>1000n</math>번 계산하는 프로그램이 0.3초간 계산해서 답을 내놓는 사이에, <math>n^2</math>번 계산하는 프로그램은 30초는 생각해야 답을 내놓을 수 있을 것이다. <math>n=1,000,000</math>라던지, <math>n=10,000,000</math>와 같은 식으로 n이 더더욱 커지면 어떻게 될까? 두 프로그램의 시간 차이는 기하급수적으로 커지게 될 것이다. | <math>n=10</math> 정도의 작은 데이터에서는 100배 더 느리다고 해도 불과 0.0001초 정도밖에 차이가 나지 않을 것이다. 데이터의 크기가 적으므로 두 프로그램 모두 매우 빠르기 때문이다! 하지만 <math>n=100,000</math>에서는 100배의 차이는 생각하는 것만큼 매우 크다. <math>1000n</math>번 계산하는 프로그램이 0.3초간 계산해서 답을 내놓는 사이에, <math>n^2</math>번 계산하는 프로그램은 30초는 생각해야 답을 내놓을 수 있을 것이다. <math>n=1,000,000</math>라던지, <math>n=10,000,000</math>와 같은 식으로 n이 더더욱 커지면 어떻게 될까? 두 프로그램의 시간 차이는 기하급수적으로 커지게 될 것이다. | ||
위의 예시에서 알 수 있었던 것은 '''계산 횟수에 붙은 상수는 별로 중요하지 않다는 것'''이다. 1,000이라는 상수가 무색해질 정도로 n이 커지면, 그 때는 n이 커짐에 따라 증가하는 계산 횟수가 훨씬 더 중요해진다.<ref>물론, 상수 <math>C=100,000,000</math> 수준으로 엄청나게 커지면 그 때는 문제가 되지만, 실제 프로그래밍에서 그런 상황은 발생하기 어렵다.</ref> 그래서 시간복잡도를 나타낼 때에는 상수는 모두 떼어버리기로 하자. <math>n</math>번 계산하든, <math>7n+1312</math>번 계산하든, <math>142857n</math>번 계산하든 모두 <math>O(n)</math>로 나타내는 것이다! 비슷한 이유로, <math>3^n+2n^3+12451n^2+33n\log n+151511</math>번 계산<ref>잔 작업의 처리가 많은 알고리즘인 듯하다</ref>하는 알고리즘의 시간 복잡도는 <math>O(3^n | 위의 예시에서 알 수 있었던 것은 '''계산 횟수에 붙은 상수는 별로 중요하지 않다는 것'''이다. 1,000이라는 상수가 무색해질 정도로 n이 커지면, 그 때는 n이 커짐에 따라 증가하는 계산 횟수가 훨씬 더 중요해진다.<ref>물론, 상수 <math>C=100,000,000</math> 수준으로 엄청나게 커지면 그 때는 문제가 되지만, 실제 프로그래밍에서 그런 상황은 발생하기 어렵다.</ref> 그래서 시간복잡도를 나타낼 때에는 상수는 모두 떼어버리기로 하자. <math>n</math>번 계산하든, <math>7n+1312</math>번 계산하든, <math>142857n</math>번 계산하든 모두 <math>O(n)</math>로 나타내는 것이다! 비슷한 이유로, <math>3^n+2n^3+12451n^2+33n\log n+151511</math>번 계산<ref>잔 작업의 처리가 많은 알고리즘인 듯하다</ref>하는 알고리즘의 시간 복잡도는 <math>O(2^n)</math><ref><math>3^n</math>도 O 표기법으로는 <math>2^n</math>와 같다. 물론, <math>150^n</math>라던지 <math>14500^n</math>와 같은 시간 복잡도와도 같은 시간 복잡도를 나타내는 것이지만, 가장 간단한 형태인 <math>2^n</math>로 나타내는 것.</ref>로 간단히 나타낼 수 있다. | ||
위의 소스들의 시간 복잡도는 어떻게 쓸 수 있을까? 소스 1은 <math>O(N)</math>의 시간 복잡도를, 소스 2는 <math>O(1)</math>의 시간 복잡도를 가지게 된다는 것을 알 수 있다. 직관적으로도 알 수 있듯이, <math>O(1)</math>의 알고리즘이 <math>O(N)</math>의 알고리즘보다 더 빠른 알고리즘이라고 할 수 있다. | 위의 소스들의 시간 복잡도는 어떻게 쓸 수 있을까? 소스 1은 <math>O(N)</math>의 시간 복잡도를, 소스 2는 <math>O(1)</math>의 시간 복잡도를 가지게 된다는 것을 알 수 있다. 직관적으로도 알 수 있듯이, <math>O(1)</math>의 알고리즘이 <math>O(N)</math>의 알고리즘보다 더 빠른 알고리즘이라고 할 수 있다. |