Картографиране на числови диапазони към отделни елементи с достъп O(1).

Ако вашите i,k,...,z са произволни, тогава не идва на ум алгоритъм с времево ограничение O(1) и разумно пространствено ограничение ‹ O(N). Ако има някаква закономерност във вашите граници, тогава, разбира се, можете да я използвате: напр. ако всеки диапазон съдържа четен брой елементи, тогава просто решение е да имате справочна таблица, която е достъпна чрез [i_N/2]. В общия случай трябва да имате съответстваща сгъваема функция за вашето число 0...N - такава, която удовлетворява ограничението k-mapping(i) != k-mapping(i+1) => сгъваема функция (i) != сгъваема функция(i+1).

Ако само някои елементи във вашата карта са достъпни често, можете също така да изградите кеш за картографирането, което води до O(1) в случай на попадение в кеша и O(lookup-function) за пропуск в кеша. Разбира се, търсенето в кеша ще повлияе на времето, изразходвано за всеки елемент, дори в случай на пропуск в кеша, но няма да повлияе на O-сложността на вашия алгоритъм.

редактиране

По принцип това, което искате да приложите, може да бъде изразено като израз на Pascal case с набори като етикети:

case n of 
0..i-1:
  value:=0;
i..i+k-1:
  value:=1;
// ...
i+k+...+z+2..N-1:
  value:=K;
end

За този проблем търсенето в Google наистина показва интересна статия:

Тази статия описва нова схема за изграждане на статични дървета за търсене, като се използват многопосочни дървета за търсене с основа. [...] Ние показваме, че за редки набори от случаи методът произвежда средно по-бърз код от съществуващите методи, изисквайки O(1) време с малка константа за средно търсене.

Erlingsson, Krishnamoorthy, Raman: Ясен и ефективен анализ на случаи

Уви, нямате рядък набор от случаи, но доколкото виждам, алгоритъмът трябва да изисква само минимална адаптация за плътни набори от случаи, които имат много последователни резултати.

За общия проблем за създаване на ефективен код за оператори на случай, Zhao и Amarla имат интересен документ, който използва профилиране, за да постигне нещо подобно на използването на кеш. Техният документ също е интересен за свързания работен раздел, който препраща към документ от Kannan и Proebsting (Корекция за създаване на добър код за оператора на случая.), който изисква O (n^2) време за настройка за клъстериране. Въпреки това нямам достъп до този документ и изглежда, че това ще създаде само изключително оптимизирано дърво за търсене, което води до време на изпълнение от O(log(n)).

Ако разбирам въпроса правилно, трябва да можете да изчислите картографирането директно с помощта на div mod. (Вижте обяснение на операторите в C)

Например в python

def my_map(n,k,i):
  elements_per_bin = n/k if n%k is 0 else n/k + 1  #in case n is exactly divisible by k
  return i/elements_per_bin    

Като пример, нека n=10, k=3

>>> n=10
>>> k=3
>>> def f(i):
      return my_map(n,k,i)
>>> range(n)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> map(f,range(n))
[0, 0, 0, 0, 1, 1, 1, 1, 2, 2]

Така че {0,1,2,3}->0, {4,5,6,7}->1 и така нататък.

Предполагам, че вече имате данните от оригиналния масив/структура на данни в паметта някъде. Вече трябва да можете да го индексирате, като изчислите индекса на масива от картографирането (може да се наложи да изградите обратна функция на my_map).

Изчисляването на индекса е O(1) и вие използвате само пространството от оригиналния масив.

Съжалявам, ако съм разбрал погрешно картографирането.