Определение нотации big-O состоит в том, что ее аргумент является функцией ( f (x) ), которая в качестве переменной в функции ( x ) стремится к бесконечности, существует постоянная K , так что функция целевой стоимости будет меньше, чем Kf (x) . Обычно f выбирается как наименьшая такая простая функция, чтобы условие выполнялось. (Совершенно очевидно, как поднять вышесказанное для нескольких переменных.)
Это важно, потому что K - который вам не требуется указывать - позволяет скрывать все множество сложных действий. Например, если ядром алгоритма является O (n 2 ), он допускает все виды других O (1), O (logn), O (n), O (nlogn), O ( n 3/2 ) и т. д., поддерживающие скрываемые биты, , даже если для реалистичных входных данных эти части действительно являются доминирующими. Это верно, это может вводить в заблуждение! (Некоторые из более красивых алгоритмов bignum обладают этим свойством по-настоящему. Ложь с математикой - замечательная вещь.)
Так, куда это идет? Что ж, вы можете предположить, что int является достаточно фиксированным размером (например, 32-битным) и использовать эту информацию, чтобы пропустить много проблем, и выделить фиксированный размер массивов битов флага для хранения всех информация, которая вам действительно нужна. Действительно, используя два бита для каждого потенциального значения (один бит, чтобы сказать, видели ли вы значение вообще, другой, чтобы сказать, напечатали ли вы его), вы можете обрабатывать код с фиксированным фрагментом памяти размером 1 ГБ. Это даст вам достаточно информации о флаге, чтобы справиться с таким количеством 32-битных целых чисел, которое вы, возможно, когда-либо захотите обработать. (Черт, это даже практично на 64-битных машинах.) Да, потребуется некоторое время, чтобы настроить этот блок памяти, но он постоянен, поэтому формально O (1) и поэтому выпадает из анализа. Учитывая это, вы получаете постоянное (но колоссальное) потребление памяти и линейное время (вы должны посмотреть на каждое значение, чтобы увидеть, новое оно, увиденное один раз и т. Д.), И это именно то, о чем просили.
Хотя это подвох. Вы также можете попробовать отсканировать список ввода, чтобы определить диапазон, позволяющий использовать меньше памяти в обычном случае; опять же, это добавляет только линейное время, и вы можете строго ограничить требуемую память, как указано выше, так что она постоянна. Еще больше хитрости, но формально законно.
[EDIT] Пример C кода (это не C ++, но я не очень хорош в C ++; главное отличие будет в том, как распределяются и управляются массивы флагов):
#include <stdio.h>
#include <stdlib.h>
// Bit fiddling magic
int is(int *ary, unsigned int value) {
return ary[value>>5] & (1<<(value&31));
}
void set(int *ary, unsigned int value) {
ary[value>>5] |= 1<<(value&31);
}
// Main loop
void print_repeats(int a[], unsigned size) {
int *seen, *done;
unsigned i;
seen = calloc(134217728, sizeof(int));
done = calloc(134217728, sizeof(int));
for (i=0; i<size; i++) {
if (is(done, (unsigned) a[i]))
continue;
if (is(seen, (unsigned) a[i])) {
set(done, (unsigned) a[i]);
printf("%d ", a[i]);
} else
set(seen, (unsigned) a[i]);
}
printf("\n");
free(done);
free(seen);
}
void main() {
int a[] = {1,0,-2,4,4,1,3,1,-2};
print_repeats(a,sizeof(a)/sizeof(int));
}