Каждый ответ, который в настоящее время отвечает на этот вопрос, говорит вам, что 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;
}
Это потому, что мы должны перебирать массив, проверяя каждый элемент по одному.