5

someone has an idea how can I do that ?

thanks

8 Answers8

5

If you need to do something to each element of a set of n elements, you cannot do it with better than O(n) performance.

Robert Gamble
  • 106,424
  • 25
  • 145
  • 137
  • This is true if you take the question at face value. That's why I think the question is misleading (and why I suspect it is a homework question). – user38051 Nov 19 '08 at 22:10
4

If you mean "initialize a dense array of N items in a time independent of N", then it is physically impossible. A dense array has a storage space that grows linearly with the number of items, and it will take a linear amount of time to initialize this space.

You can have constant-time initialization using a sparse array. That is essentially an associative array (or hashmap, or dictionary, or table, depending on the language) which initializes items when they are first accessed.

ddaa
  • 52,890
  • 7
  • 50
  • 59
2

I think its just a simple syntax question. In C++ you can do this:

int foo[1000] = {0};

All values in array are now 0

While it looks like its done in constant time, it still O(n)

Pyrolistical
  • 27,624
  • 21
  • 81
  • 106
2

It can be Done!

You can initialize an array in O(1) worst-time and O(1) extra space, and it can be improved to using only 1 extra bit of memory.

Both can be found in this Paper, explained simply in this Article, and implemented in the Farray project.
Full disclosure - the last two were written by me.

It is the state-of-the-art Initializable array, and will probably stay that. The above paper proves that without the extra bit - the fill (init) operation should take Ө(n) time, even for amortized/randomized algorithms.

Tom
  • 129
  • 2
  • 8
1

Actually, it is possible, but only with hardware help. On software, you will have to do a number of steps proportional to n, thus it is O(n); on hardware, however, you can wire things so that all elements of the array are set in parallel.

This is in fact a time/space tradeoff; while before one needed O(n) time, now one needs O(n) circuit elements but can do the operation in O(1) time.

And it is actually a common thing to do. A lot of hardware has a reset input which, when asserted, sets the whole hardware to a known state. This can involve for instance zeroing the whole memory.

CesarB
  • 43,947
  • 7
  • 63
  • 86
  • But the problem is you'll never have n circuits in the real world. It depends if the question is a theory question or not. – Pyrolistical Nov 19 '08 at 22:46
  • @Pyrolistical: when it is some sort of reset input for the memory, you already have n circuits in the real world. The same happens for the clock input. Of course, not all memory chips will have a reset input which actually clears the memory... And if you are programming for a FPGA, all bets are off. – CesarB Nov 19 '08 at 22:53
  • Big O notation denotes asymptotic complexity: when the variable (here, the size of the array) tends towards infinity. You cannot have infinity circuit elements, therefore you cannot have O(1) initialization. Matter solved. – ddaa Nov 19 '08 at 22:57
  • Well that could work, but that's now how computers work in the real world. If you have a large array, you'll be fetching parts of it from main memory and never be able to reset the entire array at once. – Pyrolistical Nov 19 '08 at 22:59
  • @ddaa: if you cannot have infinity circuit elements, you cannot have an array with infinity elements. The number of circuit elements is always at least proportional to the number of array elements, whether they have a reset input or not. – CesarB Nov 19 '08 at 23:02
1

you can initialize an array with a constant value in O(1) time. but it requires extra memory.

have a look at Initializing an array in constant time

chirag90
  • 2,211
  • 1
  • 22
  • 37
akiva zonenfeld
  • 11
  • 4
  • Actually a better algorithm is known, such that the extra 2n memory words are not needed anymore. It is based on the one you mentioned, but uses only 1 extra bit of memory. Read the [Article](https://link.medium.com/Q8YbkDJX2bb) I've written about it. – Tom Dec 09 '20 at 01:20
1

You can do it in O(1), if you calculate the runtime with an Amortized Analysis over all future read actions. You just have to initialize your element on demand (the first time its read).

schmijos
  • 8,114
  • 3
  • 50
  • 58
-1

No. It's physically impossible. However, you can use vector instructions to make it some O(n * 1/k) time, where k is the width of a vector setter instruction. That's still O(n), but the constant is shrunk.

Paul Nathan
  • 39,638
  • 28
  • 112
  • 212