[big-o] “O (1) 액세스 시간”은 무엇을 의미합니까?

현재이 질문에 응답하는 모든 답변은 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;
}

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

답변