Tell me please, is there such a data structure for storing multidimensional information, with the complexity of searching for O (log n) or O (1)?

The complexity of adding, removing, or modifying elements is not so unimportant.

  • Can a hash table? In the absence of collisions O (1). - alexlz

3 answers 3

  • For the R-tree, for example, the algorithmic complexity of the SEARCH, operation SEARCH, which is performed in O(lgN) with degradation to O(N) in the case of Minimum Bounding Volumes overlapping of the inserted objects, is proved.

  • In practice, as far as I know, the case with degradation to O(N) is not very common.

  • If you just need to index a number of multidimensional objects and do not need the ability to respond to the query "return all the objects included in the specified Minimum Bounding Volume, " you can come up with a hash function for your objects and insert them into one hash table.

However, as intuition tells me, it’s not about that.

  • Yes, your intuition did not let you down. And what does a degradation case mean? Why will the search worsen? - cyberdream
  • Thanks, now I see. - cyberdream
  • @cyberdream - Well, suppose you put in a two-dimensional R-tree a sequence of rectangles from smallest to largest and such that each next one includes the previous one (and, accordingly, all the previous ones): ---------------------------- | ---------------- | | ---------------- | | | ---- | | | | | | | | | | ---- | | | | | | | ---------------- | | | ---------------------------- - Costantino Rupert
  • - For this case, if you make a SEARCH (Best_Small_Rectangle) operation, its algorithmic complexity will be O (N) regardless of the partitioning method in R-tree, which will be the worst case for this data structure. - Again, in practice, such partitions occur quite rarely, so on average they say about O (lgN). - Costantino Rupert

You can at least include structures with the desired difficulty of searching each other. For example:

 megamap = HashMap<Координата1, HashMap<Координата2, Значение>>() megamap.get(X).get(Y) - получить значение

If the number of coordinates in your multidimensional structure is fixed (in Example 2), then asymptotically the speed will remain the same.

    found an interesting report on a similar topic of MMRO - On optimizing the search for multidimensional data in recognition