What does "O(1) access time" mean?

I have seen this term "O(1) access time" used to mean "quickly" but I don't understand what it means. The other term that I see with it in the same context is "O(n) access time". Could someone please explain in a simple way what these terms mean?

See Also

What is Big O notation? Do you use it?

Big-O for Eight Year Olds?

---

You're going to want to read up on Order of complexity.

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

In short, O(1) means that it takes a constant time, like 14 nanoseconds, or three minutes no matter the amount of data in the set.

O(n) means it takes an amount of time linear with the size of the set, so a set twice the size will take twice the time. You probably don't want to put a million objects into one of these.

---

In essence, It means that it takes the same amount of time to look up a value in your collection whether you have a small number of items in your collection or very very many (within the constraints of your hardware)

O(n) would mean that the time it takes to look up an item is proportional to the number of items in the collection.

Typical examples of these are arrays, which can be accessed directly, regardless of their size, and linked lists, which must be traversed in order from the beginning to access a given item.

The other operation usually discussed is insert. A collection can be O(1) for access but O(n) for insert. In fact an array has exactly this behavior, because to insert an item in the middle, You would have to move each item to the right by copying it into the following slot.

---

Every answer currently responding to this question tells you that the O(1) means constant time (whatever it happens to measuring; could be runtime, number of operations, etc.). This is not accurate.

To say that runtime is O(1) means that there is a constant c such that the runtime is bounded above by c , independent of the input. For example, returning the first element of an array of n integers is O(1) :

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

But this function is O(1) too:

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

The runtime here is bounded above by 1 year, but most of the time the runtime is on the order of nanoseconds.

To say that runtime is O(n) means that there is a constant c such that the runtime is bounded above by c * n , where n measures the size of the input. For example, finding the number of occurrences of a particular integer in an unsorted array of n integers by the following algorithm is 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;
}

This is because we have to iterate through the array inspecting each element one at a time.

链接地址: http://www.djcxy.com/p/39664.html

上一篇: “真实世界”中的O复杂性评估？

下一篇: “O（1）访问时间”是什么意思？