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

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

---

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

또한보십시오

• Big O 표기법은 무엇입니까? 당신은 그것을 사용합니까?
• 8 살의 빅오?

---

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

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

간단히 말해서 O (1)은 14 나노초와 같이 일정한 시간이 걸리거나 세트의 데이터 양에 관계없이 3 분이 걸린다는 것을 의미합니다.

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

---

본질적으로 컬렉션에있는 항목의 수가 적든 매우 많든 (하드웨어의 제약 내에서) 컬렉션에서 값을 찾는 데 동일한 시간이 걸립니다.

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

일반적인 예로는 크기에 관계없이 직접 액세스 할 수있는 배열과 주어진 항목에 액세스하기 위해 처음부터 순서대로 순회해야하는 연결 목록이 있습니다.

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

---

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

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

---

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

O (N)은 항목에 액세스하는 시간이 컬렉션의 항목 수 (N)에 비례 함을 의미합니다.

---

O (1)은 반드시 "빠르게"를 의미하지는 않습니다. 이는 걸리는 시간이 일정 하며 함수에 대한 입력 크기를 기반으로 하지 않음 을 의미합니다. 상수는 빠르거나 느릴 수 있습니다. O (n)은 함수에 걸리는 시간이 n으로 표시되는 함수에 대한 입력 크기에 정비례하여 변경됨을 의미합니다. 다시 말하지만, 그것은 빠르거나 느릴 수 있지만, n의 크기가 증가함에 따라 느려질 것입니다.

---

Big O 표기법 이라고하며 다양한 알고리즘에 대한 검색 시간을 설명합니다.

O (1)은 최악의 실행 시간이 일정 함을 의미합니다. 대부분의 경우 컬렉션을 우연히 검색 할 필요가 없으며 검색중인 내용을 즉시 찾을 수 있습니다.

---

"Big O 표기법"은 알고리즘의 속도를 표현하는 방법입니다. n알고리즘이 작업하는 데이터의 양입니다. O(1)이는 아무리 많은 데이터가 있어도 일정한 시간에 실행된다는 것을 의미합니다. O(n)데이터 양에 비례 함을 의미합니다.

---

O(1)데이터 세트 n에 관계없이 항상 같은 시간에 실행됩니다. O (1)의 예는 인덱스로 요소에 액세스하는 ArrayList입니다.

O(n)선형 순서라고도하는 성능은 입력 데이터의 크기에 정비례하여 선형 적으로 증가합니다. O (n)의 예는 임의의 위치에서 ArrayList 삽입 및 삭제입니다. 임의의 위치에서 각 후속 삽입 / 삭제로 인해 ArrayList의 요소가 선형 구조를 유지하기 위해 내부 배열의 왼쪽 오른쪽으로 이동하게되며, 새 배열의 생성 및 이전 요소의 복사에 대해서는 말할 것도 없습니다. 따라서 처리 시간이 많이 소요되는 새로운 어레이로 인해 성능이 저하됩니다.

---

Basically, O(1) means its computation time is constant, while O(n) means it will depend lineally on the size of input - i.e. looping through an array has O(n) - just looping -, because it depends on the number of items, while calculating the maximum between to ordinary numbers has O(1).

Wikipedia might help as well: http://en.wikipedia.org/wiki/Computational_complexity_theory

---

The easiest way to differentiate O(1) and O(n) is comparing array and list.

For array, if you have the right index value, you can access the data instantly. (If you don't know the index and have to loop through the array, then it won't be O(1) anymore)

For list, you always need to loop through it whether you know the index or not.

---

It means that access time is constant. Whether you're accessing from 100 or 100,000 records, the retrieval time will be the same.

In contrast, O(n) access time would indicate that the retrieval time is directly proportional to the number of records you're accessing from.

---

It means that the access takes constant time i.e. does not depend on the size of the dataset. O(n) means that the access will depend on the size of the dataset linearly.

The O is also known as big-O.

---

Introduction to Algorithms: Second Edition by Cormen, Leiserson, Rivest & Stein says on page 44 that

Since any constant is a degree-0 polynomial, we can express any constant function as Theta(n^0), or Theta(1). This latter notation is a minor abuse, however, because it is not clear what variable is tending to infinity. We shall often use the notation Theta(1) to mean either a constant or a constant function with respect to some variable. ... We denote by O(g(n))... the set of functions f(n) such that there exist positive constants c and n0 such that 0 <= f(n) <= c*g(n) for all n >= n0. ... Note that f(n) = Theta(g(n)) implies f(n) = O(g(n)), since Theta notation is stronger than O notation.

If an algorithm runs in O(1) time, it means that asymptotically doesn't depend upon any variable, meaning that there exists at least one positive constant that when multiplied by one is greater than the asymptotic complexity (~runtime) of the function for values of n above a certain amount. Technically, it's O(n^0) time.

---

Here is a simple analogy; Imagine you are downloading movies online, with O(1), if it takes 5 minutes to download one movie, it will still take the same time to download 20 movies. So it doesn't matter how many movies you are downloading, they will take the same time(5 minutes) whether it's one or 20 movies. A normal example of this analogy is when you go to a movie library, whether you are taking one movie or 5, you will simply just pick them at once. Hence spending the same time.

However, with O(n), if it takes 5 minutes to download one movie, it will take about 50 minutes to download 10 movies. So time is not constant or is somehow proportional to the number of movies you are downloading.

---

O(1) means Random Access. In any Random Access Memory, the time taken to access any element at any location is the same. Here time can be any integer, but the only thing to remember is time taken to retrieve the element at (n-1)th or nth location will be same(ie constant).

Whereas O(n) is dependent on the size of n.

---

According to my perspective,

O(1) means time to execute one operation or instruction at a time is one, in time complexity analysis of algorithm for best case.

참고URL : https://stackoverflow.com/questions/697918/what-does-o1-access-time-mean