"O (1) 액세스 시간"은 무엇을 의미합니까?

Question

나는이 용어 "O (1) 액세스 시간"이 "빠르게"를 의미하는 데 사용되었지만 그것이 무엇을 의미하는지 이해하지 못합니다. 같은 맥락에서 내가 볼 수있는 다른 용어는 "O (n) 액세스 시간"입니다. 누군가이 용어가 의미하는 바에 대해 간단한 방식으로 설명해 주시겠습니까?

또한보십시오

• 큰 O 표기법은 무엇입니까? 당신은 그것을 사용합니까?
• 8 살짜리 아이를위한 big-o?

Answer 1

당신은 복잡성의 순서로 읽고 싶을 것입니다.

http://en.wikipedia.org/wiki/big_o_notation

요컨대, O (1)은 세트의 데이터 양에 관계없이 14 나노초와 같이 일정한 시간이 걸린다는 것을 의미합니다.

o (n)은 세트의 크기로 선형 시간이 걸리므로 세트의 두 배는 시간의 두 배가 걸립니다. 당신은 아마도 이것들 중 하나에 백만 개를 넣고 싶지 않을 것입니다.

Answer 2

본질적으로, 그것은 컬렉션에 소수의 항목이 있든 매우 많은 (하드웨어의 제약 조건 내) 컬렉션에서 값을 찾는 데 같은 시간이 걸린다는 것을 의미합니다.

o (n)은 항목을 찾는 데 걸리는 시간이 컬렉션의 항목 수에 비례한다는 것을 의미합니다.

이들의 일반적인 예는 크기에 관계없이 직접 액세스 할 수있는 배열과 링크 된 목록이며, 처음부터 주어진 항목에 액세스하기 위해 순서대로 이동해야합니다.

일반적으로 논의되는 다른 작업은 삽입입니다. 컬렉션은 A (1)에 액세스 할 수 있지만 삽입에는 O (N)가 될 수 있습니다. 실제로 배열에는이 동작이 정확히이 동작이 있습니다. 중간에 항목을 삽입하려면 다음 슬롯에 복사하여 각 항목을 오른쪽으로 이동해야합니다.

Answer 3

현재이 질문에 응답하는 모든 대답은 O(1) 일정한 시간 (측정에 어떤 일이든, 런타임, 운영 수 등)를 의미합니다. 이것은 정확하지 않습니다.

런타임이라고 말하는 것 O(1) 상수가 있음을 의미합니다 c 런타임이 위로 바인딩되도록합니다 c, 입력과 무관합니다. 예를 들어, 배열의 첫 번째 요소를 반환합니다. n 정수입니다 O(1):

int firstElement(int *a, int n) {
    return a[0];
}

그러나이 기능은입니다 O(1) 도:

int identity(int i) {
    if(i == 0) {
        sleep(60 * 60 * 24 * 365);
    }
    return i;
}

여기서의 런타임은 1 년 이상이지만 대부분의 시간은 런타임이 나노초 순서에 있습니다.

런타임이라고 말하는 것 O(n) 상수가 있음을 의미합니다 c 런타임이 위로 바인딩되도록합니다 c * n, 어디 n 입력의 크기를 측정합니다. 예를 들어, 음란하지 않은 배열에서 특정 정수의 발생 수를 찾으십시오. n 다음 알고리즘의 정수입니다 O(n):

int count(int *a, int n, int item) {
    int c = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] == item) c++;
    }
    return c;
}

이것은 각 요소를 한 번에 하나씩 검사하는 배열을 반복해야하기 때문입니다.

Answer 4

o (1)는 무언가에 액세스 할 시간이 컬렉션의 항목 수와 무관하다는 것을 의미합니다.

o (n)은 항목에 액세스하는 시간이 컬렉션의 항목의 숫자 (n)에 비례한다는 것을 의미합니다.

Answer 5

o (1)이 반드시 "빠르게"를 의미하지는 않습니다. 그것은 시간이 일정하다는 것을 의미하며 ~ 아니다 함수에 대한 입력의 크기를 기준으로합니다. 상수는 빠르거나 느릴 수 있습니다. o (n)은 함수가 취하는 시간이 N 다시 말하지만, 빠르거나 느릴 수 있지만 N 크기가 증가함에 따라 느리게됩니다.

Answer 6

그것은 The라고합니다 큰 o 표기법, 다양한 알고리즘의 검색 시간을 설명합니다.

o (1)는 최악의 사례 실행 시간이 일정하다는 것을 의미합니다. 대부분의 상황에서 그것은 당신이 컬렉션을 검색 할 필요가 없다는 것을 의미합니다. 캔트는 바로 찾고있는 것을 찾습니다.

Answer 7

"큰 O 표기법"은 알고리즘의 속도를 표현하는 방법입니다. n 알고리즘이 작업하는 데이터의 양입니다. O(1) 데이터의 양에 관계없이 일정한 시간에 실행됩니다. O(n) 데이터 양에 비례한다는 것을 의미합니다.

Answer 8

O(1) 데이터 세트 n에 관계없이 항상 동시에 실행하십시오. O (1)의 예는 인덱스를 사용하여 요소에 액세스하는 배열리스트입니다.

O(n) 선형 순서라고도하는 성능은 선형으로 및 입력 데이터의 크기에 비례하여 증가합니다. O (n)의 예는 배열리스트 삽입 및 랜덤 위치에서 삭제됩니다. 무작위 위치에서 각 후속 삽입/삭제는 Arraylist의 요소가 새로운 배열 생성 및 이전의 요소 복사에 대해서는 언급하지 않고 선형 구조를 유지하기 위해 내부 배열의 왼쪽을 이동하게합니다. 고가의 처리 시간을 차지하는 새로운 배열로 성능을 해치십시오.

Answer 9

기본적으로 o (1)은 계산 시간이 일정하다는 것을 의미하고 o (n)은 의존한다는 것을 의미합니다. 직계로 입력 크기의 크기 - 즉 배열을 통한 루핑은 O (n) - 단지 루핑이 있습니다. 항목 수에 따라 다르기 때문에, 일반 숫자 사이의 최대 값은 O (1)을 가지고 있기 때문입니다.

Wikipedia도 도움이 될 수 있습니다. http://en.wikipedia.org/wiki/computational_complexity_theory

Answer 10

O (1) 및 O (n)을 구별하는 가장 쉬운 방법은 배열과 목록을 비교하는 것입니다.

배열의 경우 올바른 색인 값이있는 경우 데이터에 즉시 액세스 할 수 있습니다. (인덱스를 모르고 배열을 통해 루프 해야하는 경우 더 이상 O (1)가 아닙니다.

목록의 경우 인덱스를 알고 있든 없든 항상 반복해야합니다.

Answer 11

그것은 액세스 시간이 일정하다는 것을 의미합니다. 100 또는 100,000 레코드에서 액세스하든 검색 시간은 동일합니다.

대조적으로, O (n) 액세스 시간은 검색 시간이 액세스하는 레코드 수에 직접 비례한다는 것을 나타냅니다.

Answer 12

이는 액세스가 일정한 시간이 걸린다는 것을 의미합니다. 즉, 데이터 세트의 크기에 의존하지 않습니다. o (n)은 액세스가 데이터 세트의 크기에 따라 선형으로 의존 함을 의미합니다.

O는 Big-O라고도합니다.

Answer 13

알고리즘 소개 : Cormen, Leiserson, Rivest & Stein의 두 번째 판

상수는 어느 정도의 다항식이므로, 우리는 theta (n^0) 또는 theta (1)과 같은 일정한 기능을 표현할 수 있습니다. 그러나이 후자의 표기법은 변수가 무한대를 돌보는 경향이 확실하지 않기 때문에 경미한 남용입니다. 우리는 종종 일부 변수와 관련하여 상수 또는 일정한 함수를 의미하기 위해 표기법 (1)을 사용해야합니다. ... 우리는 o (g (n))로 표시됩니다 ... 함수 세트 f (n)는 0 <= f (n) <= c*g (n)이되도록 양의 상수 c와 n0이 존재하도록합니다. 모든 n> = n0에 대해. ... f (n) = theta (g (n))은 f (n) = o (g (n))을 의미합니다. theta 표기법은 O 표기법보다 강력하기 때문입니다.

알고리즘이 O (1) 시간에 실행되는 경우, 비대칭 적으로 변수에 의존하지 않음을 의미합니다. 즉, 하나를 곱할 때 함수의 점근 적 복잡성 (~ 런타임)보다 큰 양의 상수가 존재 함을 의미합니다. N의 값은 일정량 이상입니다. 기술적으로, 그것은 O (n^0) 시간입니다.

Answer 14

여기 간단한 비유가 있습니다. O (1)와 함께 온라인으로 영화를 다운로드한다고 상상해보십시오. 영화 하나를 다운로드하는 데 5 분이 걸리면 20 개의 영화를 다운로드하는 데 여전히 동시에 시간이 걸립니다. 따라서 다운로드하는 영화 수는 중요하지 않으며 동시에 (5 분) 한 영화이든 20 개의 영화이든 동시에 시간이 걸립니다. 이 비유의 정상적인 예는 영화 도서관에 갈 때, 한 영화를 찍거나 5 번을 찍을 때 단순히 한 번에 선택하는 것입니다. 따라서 동시에 지출합니다.

그러나 O (N)의 경우 한 영화를 다운로드하는 데 5 분이 걸리면 10 개의 영화를 다운로드하는 데 약 50 분이 걸립니다. 따라서 시간은 일정하지 않거나 다운로드하는 영화 수에 비례합니다.

Answer 15

o (1)는 임의의 액세스를 의미합니다. 임의의 액세스 메모리에서 모든 위치에서 모든 요소에 액세스하는 데 걸리는 시간은 동일합니다. 여기서 시간은 정수 일 수 있지만, 기억해야 할 유일한 것은 (n-1) th에서 요소를 검색하는 데 걸리는 시간 또는 nth 위치는 동일합니다 (즉, 일정).

반면 O (n)은 n의 크기에 따라 다릅니다.

Answer 16

내 관점에 따라

o (1) 한 번에 하나의 작업 또는 명령을 실행하는 시간은 하나이며 최상의 경우 알고리즘의 복잡성 분석을 의미합니다.