알고리즘의 효과에 대한 테이블을 추론 할 수 없습니다

Question

나는 완전히 확실하지 않다 다음 표

Alt Text http://files.getdropbox.com/u/175564/algtranslation.png

테이블은 알고리즘 복잡성이 주어진 크기 일 때 왼쪽 열에서 주어진 시간 제한에서 해결할 수있는 문제의 크기를 제공합니다.

나는 테이블의 공제에 관심이있다.

테이블은 나에게 그것을 제안합니다

• O (n) = 1 초 만에 10m (이것은 현재 컴퓨터의 힘 인 것 같습니다)
• N 처리 할 항목 수입니다 # Guffa에게 감사합니다!

O (n * log (n))의 열의 값이 어떻게 추론되었는지 잘 모르겠습니다.

1. 값 0.5m를 어떻게 추론 할 수 있습니까? O (n * log (n)) 또는 o (n^2)의 경우?

Answer 1

나는이 테이블이 단순히 매우 대략적인 그림을 제공한다고 생각합니다. N 고정 된 시간 (1 초, 1 분, 1 시간, 1 일 또는 1 년)이 처분 할 때 다른 종류의 복잡성이 될 수 있습니다.

예를 들어 O (n^3) :

 1 second: 200^3 = 8 000 000 (roughly 10 million, given in O(n) column)
 1 minute: 850^3 = 614 125 000 (roughly 600 million, given in O(n) column))
 1 hour: 3000^3 = 27 000 000 000 (somewhat roughly 35 billion, given in O(n) column)

보시다시피, 숫자는입니다 매우 거친 근사. 저자는 그의 요점을 설명하기 위해 멋진 라운드 숫자를 사용하고 싶었던 것 같습니다.

Answer 2

아니요, N은 초 수가 아니며 처리 할 항목 수입니다.

o (n)은 항목을 처리하는 시간이 항목 수에 선형임을 의미합니다.

o (n²)는 항목을 예상하는 시간이 항목 수의 제곱과 관련이 있음을 의미합니다. 품목 수를 두 배로 늘리면 처리 시간이 4 배 더 길어집니다.

보다: 큰 o 표기법

테이블은 항목 당 고정 된 양의 작업이 있다고 가정하지만, 큰 O 표기법은 알고리즘이 항목 수 변경에 어떻게 반응하는지에 대해서만 지정하지만 항목 당 얼마나 많은 작업이 있는지에 대해 아무것도 말하지 않습니다.

편집하다:
테이블의 X 축을 따르는 값은 항목 당 작업이 동일하다는 가정에 근거한 근사치입니다. 예를 들어 O (n²)의 3000 값은 10 백만의 제곱근에서 둥글게됩니다. 10 백만의 입방 뿌리는 200이 아니며 ~ 215.44입니다.

실제 상황에서는 두 개의 알고리즘이 항목 당 동일한 양의 작업을 거의 수행하지 않습니다. O (log n)가있는 알고리즘은 일반적으로 같은 목적으로 O (n) 알고리즘보다 항목 당 더 많은 작업을 수행하지만 대부분의 상황에서는 여전히 더 잘 확장되기 때문에 여전히 선호됩니다.

Answer 3

초당 10,000,000 개의 OPS를 수행 할 수있는 경우 N = 500,000을 설정하고 N * log (N) = 500,000 * LOG2 (500,000) = 500,000 * 18 = 9,000,000 OPS를 계산하면 "초"의 목적으로 약 10,000,000입니다. 분류.

마찬가지로, n = 3,000에서는 n^2 = 9,000,000을 얻습니다. 따라서 모든 라인에서 운영 수는 거의 동일합니다.