On 13 Mrz., 23:42, "Andrei Alexandrescu (See Website For Email)"
<SeeWebsiteForEm...@[EMAIL PROTECTED]
> wrote:
> Michael.Boehni...@[EMAIL PROTECTED]
wrote:
> > On 13 Mrz., 09:42, "Andrei Alexandrescu (See Website For Email)"
[..]
>
> > Sorry, the problem is solvable, without any extra data storage but for
> > a single iterator (or index) used for traversing the list and one
> > helper variable for exchanging elements.
>
> That restates what I said, so I guess "Indeed" should replace "Sorry"
:o).
The "sorry" refers to the O(log N) complexity estimate.
> > For working on N elements its
> > complexity is O(N) time and O(N) space - each list element needs to be
> > touched O(1) times.
>
> The complexity is O(N) time and O(log N) space.
How do you store N integers in log N space? If you refer to extra
space in excess to the storage for the ints itself only, there is no
need for it. One extra int for exchanging elements is enough. O(1)...
> > If the container is initially unsorted, it needs to sorted first. The
> > complexity of sorting is O( N log N ) time and O(N) space. For space
> > complexity this means no change, the time complexity of the sorting
> > dominates the uniqueness algorithm.
>
> The problem said that the array was already sorted.
*If*... just wanted to point out that the pre-sort makes a difference.
best,
Michael
--
[ See http://www.gotw.ca/resources/clcm.htm
for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
