나는 n의 충분히 작은 값에 대해 O (n)이 마치 O (1) 인 것처럼 생각 / 처리 될 수 있다고 여러 번 들었습니다.

예 :

그렇게하는 동기는 O (1)이 항상 O (lg n)보다 낫고 항상 O (n)보다 낫다는 잘못된 생각에 근거합니다. 작업의 점근 적 순서는 실제 상황에서 문제의 크기가 실제로 커지는 경우에만 관련이 있습니다. n이 작게 유지되면 모든 문제는 O (1)입니다!

충분히 작은 것은 무엇입니까? 10? 100? 1,000? “우리는 이것을 더 이상 무료 작업처럼 취급 할 수 없습니다”라고 말합니까? 경험의 규칙이 있습니까?

도메인 또는 사례별로 다를 수 있지만이 방법에 대한 일반적인 경험 규칙이 있습니까?

답변

모든 차수는 상수 포함하며 실제로는 몇 개입니다. 항목 수가 충분히 많으면 상수가 관련이 없습니다. 문제는 해당 상수가 지배하기에 충분한 항목 수가 적은지 여부입니다. $C$

여기에 시각적으로 생각하는 방법이 있습니다.

모두 Y 축의 시작점을 결정하는 시작 상수가 있습니다. 각각은 또한 얼마나 빠르게 증가 할 것인지를 결정하는 중요한 상수 가지고 있습니다. $C$

들면 , 시간을 결정한다. $O (1)$ $C$
$O (n)$ 은 실제로 이며 여기서 는 각도를 결정합니다. $C \times n$ $C$
$O (n^{2})$ 는 실제로 이며 여기서 는 곡선의 선명도를 결정합니다. $(C \times n)^{2}$ $C$

어떤 알고리즘을 사용해야하는지 결정하려면 런타임이 교차하는 지점을 추정해야합니다. 예를 들면, 높은 시작 시간 또는 고와 용액 내지 An 잃게 낮은 시작 시간 및 저와 용액 항목의 상당히 많은 수의. $O (1)$

O(1)

$C$

$O (n)$

O(n)

$C$

여기 실제 사례가 있습니다. 마당을 가로 질러 많은 벽돌을 움직여야합니다. 손으로 한 번에 몇 개씩 움직이거나 한 번의 여행으로 거대하고 느린 백호우를 들고 들어 올릴 수 있습니다. 세 개의 벽돌이 있다면 당신의 대답은 무엇입니까? 삼천이 있다면 당신의 대답은 무엇입니까?

다음은 CS 예입니다. 항상 정렬 된 목록이 필요하다고 가정 해 봅시다. 순서대로 유지되는 트리를 사용할 수 있습니다 . 또는 정렬되지 않은 목록을 사용하고 에서 모든 삽입 또는 삭제 후에 다시 정렬 할 수 있습니다 . 트리 연산이 복잡하고 (상수가 높음) 정렬이 매우 간단하므로 (상수가 낮음) 목록이 수백 또는 수천 개의 항목으로 이길 수 있습니다. $O (\log n)$

O(log⁡n)

$O (n \log n)$

O(nlog⁡n)

이런 종류의 일을 눈으로 볼 수는 있지만 결국 벤치마킹이 그 일을합니다. 당신은 또한 당신이 일반적으로 가질 수있는 품목의 수를 주시하고, 더 많은 물건을 나눠야 할 위험을 완화해야합니다. 또한 ” 항목 보다 성능이 빠르게 저하 됩니다”또는 “최대 세트 크기는 ” 라고 가정합니다 . $X$

$X$

이러한 요구 사항은 변경 될 수 있으므로 이러한 종류의 결정을 인터페이스 뒤에 두는 것이 중요합니다. 위의 트리 /리스트 예제에서 트리 또는 목록을 노출하지 마십시오. 그렇게하면, 가정이 틀리거나 더 나은 알고리즘을 찾으면 마음을 바꿀 수 있습니다. 항목 수가 증가함에 따라 하이브리드 및 동적 전환 알고리즘을 수행 할 수도 있습니다.

답변

이것은 이미 게시 된 답변에 대해 피기 백이지만 다른 관점을 제공 할 수 있습니다.

이 질문은 “충분히 작은 n 값”에 대해 논하고있다 . Big-O의 요점은 처리되는 내용에 따라 처리가 어떻게 성장하는지 설명하는 것입니다. 처리되는 데이터가 작게 유지되는 경우 성장에 관심이 없기 때문에 Big-O에 대해 논의하는 것은 무의미합니다 (발생하지 않음).

달리 말하면, 거리에서 아주 짧은 거리를 가면 걷거나 자전거를 타거나 운전하는 것이 똑같이 빠를 수 있습니다. 자동차 열쇠를 찾는 데 시간이 걸리거나 자동차에 가스가 필요한 경우 등을 걷는 것이 더 빠를 수도 있습니다.

작은 n 의 경우 편리한 것을 사용하십시오.

크로스 컨트리 여행을하는 경우 운전, 가스 마일리지 등을 최적화하는 방법을 찾아야합니다.

답변

인용문은 다소 모호하고 정확하지 않습니다. 해석 할 수있는 방법은 3 가지 이상 있습니다.

문자 그대로의 수학적 요점은 크기 제한이있는 인스턴스에만 관심이 있다면 가능한 많은 인스턴스가 있다는 것입니다. 예를 들어, 최대 100 개의 정점에는 유한하게 많은 그래프가 있습니다. 유한 한 수의 인스턴스 만있는 경우 원칙적으로 가능한 모든 인스턴스에 대한 모든 응답의 룩업 테이블을 구성하여 문제를 해결할 수 있습니다. 이제 입력이 너무 크지 않은지 먼저 확인하여 정답을 찾을 수 있습니다 (일정 시간이 걸립니다 : 입력이 보다 긴 경우 $k$

유효하지 않은 경우) 표에서 답변을 찾아보십시오. 시간이 오래 걸립니다. 표에 고정 된 수의 항목이 있습니다. 그러나 테이블의 실제 크기는 아마도 엄청나게 클 수도 있습니다. 백 정점에는 유한 한 수의 그래프 만 있다고했는데 사실입니다. 유한 한 수가 관측 가능한 우주의 원자 수보다 더 크다는 것입니다.

더 실용적인 점은 알고리즘의 실행 시간이 라고 말할 때 일부 상수 대해 무증상 단계 임을 의미합니다 . 즉, 모든 에 대해 알고리즘이 대략 단계를 취하도록 일정한 있습니다. 그러나 아마도 $Θ (n^{2})$

Θ(n2)

$c n^{2}$

cn2

$C$

$n_{0}$

$n \geq n_{0}$

n≥n0

$c n^{2}$

cn2

$n_{0} = 100, 000, 000$

n0=100,000,000

그보다 훨씬 작은 크기의 인스턴스에만 관심이 있습니다. 점근 2 차 경계는 소규모 인스턴스에도 적용되지 않을 수 있습니다. 운이 좋을 수도 있고 작은 입력에서 더 빠를 수도 있습니다 (또는 운이 좋지 않아 느려질 수도 있습니다). 예를 들어 small , 경우 상수가 나쁜 선형 알고리즘보다 상수가 좋은 2 차 알고리즘을 실행하는 것이 좋습니다. 실제 사례는 가장 효율적인 행렬 곱셈 알고리즘 ( 시간이 실행되는 Coppersmith-Winograd의 변형 )이 Strassen의 때문에 실제로 거의 사용되지 $n$

$n^{2} < 1000 n$

n2<1000n

$O (n^{2.3729})$

O(n2.3729)

알고리즘은 행렬이 실제로 크지 않으면 더 빠릅니다. $O (n^{2.8074})$

O(n2.8074)

세 번째 요점은 이 작 으면 및 심지어 이 작다는 것입니다. 예를 들어, 수천 개의 데이터 항목을 정렬해야하고 한 번만 정렬해야하는 경우 정렬 알고리즘으로 충분합니다. a $n$

$n^{2}$

$n^{3}$

$Θ (n^{2})$

Θ(n2)

알고리즘은 여전히 데이터를 정렬하기 위해 수천만 개의 명령이 필요할 것인데, 이는 초당 수십억 개의 명령을 수행 할 수있는 CPU에서 전혀 시간이 걸리지 않습니다. 좋아, 메모리 액세스도 있지만 느린 알고리즘조차도 1 초도 걸리지 않으므로 간단하고 느린 알고리즘을 사용하고 복잡하고 빠른 알고리즘을 사용하고 번개가 빠른 것을 찾는 것보다 낫습니다. 그러나 버그가 있고 실제로 데이터를 올바르게 정렬하지 않습니다.

답변

Big-O 표기법은 실제로 임의의 큰 n에 대한 동작에 대해서만 말합니다. 예를 들어, 는 마다 상수 c> 0 및 정수 있어 을 의미합니다 . $f (n) = O (n^{2})$

f(n)=O(n2)

$n_{0}$

$f (n) < c n^{2}$

f(n)<cn2

$n > n_{0}$

n>n0

대부분의 경우 상수 c를 찾을 수 있으며 "n> 0마다 f (n)은 대략 "입니다. 유용한 정보입니다. 그러나 어떤 경우에는 이것이 사실이 아닙니다. f (n) = 인 경우 이는 완전히 잘못된 것입니다. 따라서 무언가가 O (n ^ 2)라고해서 두뇌를 끄고 실제 기능을 무시할 수있는 것은 아닙니다. $c n^{2}$

cn2

$n^{2} + 10^{18}$

n2+1018

반면에 n = 1, 2 및 3의 값만 만나는 경우 실제로는 n ≥ 4에 대해 f (n)이 수행하는 작업에 차이를 만들지 않으므로 f ( n) = O (1), c = 최대 (f (1), f (2), f (3)). 그리고 그것이 충분히 작은 의미입니다. f (n) = O (1)라는 주장이 당신에게 직면하는 f (n)의 유일한 값이 "충분히 작은"경우 오도하지 않습니다.

답변

자라지 않으면 O (1)

저자의 진술은 약간 공리적입니다.

성장 순서는 증가해야 할 작업량에 어떤 일이 발생하는지 설명합니다 N. 그것이 N증가하지 않는다는 것을 알고 있다면 , 당신의 문제는 효과적 O(1)입니다.

그 기억 O(1)"빠른"을 의미하지 않습니다. 완료하는 데 항상 1 조 개의 단계가 필요한 알고리즘은 O(1)입니다. 1-200 단계에서 아무 데나 걸리는 알고리즘은 다음과 같습니다 O(1). [1]

알고리즘이 정확히 N ^ 3단계를 수행하고 5를 초과 할 수 없다는 것을 알고 있으면 N125 단계를 초과 할 수 없으므로 효과적으로 O(1)됩니다.

그러나 다시 O(1)"충분히 빠르다"는 의미는 아닙니다. 그것은 당신의 상황에 따라 다른 질문입니다. 무언가를 마치는 데 일주일이 걸리더라도 기술적으로는 신경 쓰지 않을 것 O(1)입니다.

[1] 예를 들어, 해시에서의 조회는 O(1)해시 충돌로 인해 해당 버킷에있을 수있는 항목 수에 대한 제한이없는 한 하나의 버킷에서 여러 항목을 살펴 봐야 할 수도 있습니다.

답변

이제 해시 테이블을 사용할 수 있고 해시 테이블의 특정 구현을 제외하고 O (1) 조회가 가능하지만 목록이 있으면 O (n) 조회가 있습니다. 이러한 공리를 감안할 때 모음이 충분히 작 으면이 두 가지가 동일합니다. 그러나 어떤 시점에서 그들은 분기됩니다 ... 그 시점은 무엇입니까?

실제로 해시 테이블을 빌드하면 개선 된 조회에서 얻을 수있는 이점보다 많은 이점이 있습니다. 조회 빈도와 다른 작업 빈도 에 따라 많이 달라집니다 . O (1) vs O (10)은 한 번만해도 큰 문제가되지 않습니다. 초당 수천 번 수행하면 문제는 중요합니다 (적어도 선형으로 증가하는 속도로 중요하지만).

답변

인용문은 사실이지만 (모호하지만) 인용문에도 위험이 있습니다. Imo 응용 프로그램의 모든 단계에서 복잡성을 살펴 봐야합니다.

말하기가 너무 쉽습니다. 이봐, 나는 작은 목록 만 가지고있다. 항목 A가 목록에 있는지 확인하고 싶다면 목록을 순회하고 항목을 비교하는 쉬운 루프를 작성한다.

그런 다음 buddyprogrammer는 목록을 사용해야하고 기능을보고 다음과 같습니다.이 목록에서 중복을 원하지 않으므로 목록에 추가 된 모든 항목에 대해 기능을 사용합니다.

(여전히 작은 목록 시나리오입니다.)

3 년 후, 제가 와서 사장님이 방금 큰 판매를했습니다 : 우리의 소프트웨어는 큰 전국 소매점에 의해 사용될 것입니다. 우리는 작은 가게 만 서비스하기 전에. 그리고 이제 내 상사가 맹세하고 소리를 지르는데, 왜 항상 "정상적으로 작동"했던 소프트웨어가 너무 느릴까요.

그 목록은 고객의 목록이었고 우리 고객은 100 명의 고객만을 가졌으므로 아무도 눈치 채지 못했습니다. 목록을 채우는 작업은 기본적으로 O (1) 작업이었습니다. 밀리 초보다 적게 걸리기 때문입니다. 추가 할 클라이언트가 10.000 명일 때는 그리 많지 않습니다.

그리고 원래의 나쁜 O (1) 결정 이후 몇 년 동안 회사는 거의 큰 고객을 잃었습니다. 몇 년 전에 하나의 작은 설계 / 가정 오류로 인해 발생했습니다.

Exit mobile version

How IT

언제든지 물어보세요.

“n의 작은 값의 경우 O (n)은 마치 O (1) 인 것처럼 처리 될 수 있습니다.” 수 있다고 여러

답변

답변

답변

답변

답변

자라지 않으면 O (1)

답변

답변