1
5 단계의 상각 데이터 분석 과정에서 주어진 상각 처리 된 분석 방법의 O (n)/n = 1은 어떻게됩니까? : 집계 방법?상각 처리 된 분석의 집계 방법에서 O (n)/n = 1은 어떻게됩니까
A
답변
0
짧은 대답
O (N)/N = CN/N = C = O (1)
긴 대답
우리는 의 비용을 분석하기 위해 상각 분석을 사용 시퀀스 작업의 단일 작업 비용보다. 마지막 경우 우리는 점근 적 분석을 사용합니다 (일부는 점근 적 표기법 : 쎄타, 빅 오, 빅 오메가, 리틀 오, 리틀 오메가). 그러나 일련의 작업을 수행 할 때 잘 작동하지 않습니다. 그 순서의 비용을 이해하라.
그 이유는 우리가 "일반"점근 적 분석을 적용하는 경우 우리의 예를 들어, 최악의 경우 분석 asymptotical 상한이 너무 비관적 될 수 있다는 것입니다. 고전적인 예가 동적 배열에 삽입됩니다. 요소를 동적으로 할당 된 배열에 삽입하고 배열이 가득 차면 새 배열을 정의하고 (예 : 두 배 큰) 모든 요소를 복사합니다. 대부분의 삽입은 일정 시간 (또는 O (1))에서 작동하지만, 배열을 재정의해야 할 경우 모든 요소를 복사해야하므로 선형 시간 (O (n))이 소요됩니다. .
당신은 n 개의 원소를 삽입하고 배열을 한 번만 재정의해야한다고 가정하면, 최악의 경우 각 연산은 O (n)이므로 최악의 경우 연산 순서 비용이 발생합니다 사례는 O (n^2)이며, 대부분의 작업이 최악의 경우 O (1)이고 그 중 하나만 O (n) 인 사실을 고려하면 너무 비관적으로 보입니다.
작업 시퀀스의 상환 된 비용을 (n 작업 비용)/n으로 정의합니다. 귀하의 경우 n 작업의 비용은 Big O 표기법의 정의에 따라 cn (c는 일부 상수 임)과 동일한 O (n)이며, n으로 나누면 c 만 얻을 수 있습니다.이 값은 O (1) 다시 한번, c는 단지 일정하다.