 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 1/31/2012 7:49 AM, Kevin Wampler wrote:
>
> Although I haven't done it myself, I believe if you actually do the
> complexity analysis you'll find that the lack of random access doesn't
> change the complexity of the obvious recursive algorithm except by a
> constant factor.
Ok, I actually looked at it and the obvious algorithm does take O(n
log(n)) on a linked list. But you I think you can modify it prettily
easily to run in O(n) by treating the linked list as a list of trees of
size 1, and iteratively running through the list and forming larger
trees from the smaller ones. There's probably some fiddily details to
get balancing just right while ensuring combining the sub-trees takes
O(1) though, but I think it'll all work out.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 1/31/2012 8:29 AM, Warp wrote:
>
> Since elements in a BST usually have pointers to each other anyways,
> and since merging two linked lists can be done without requiring any
> additional memory, this whole operation might be possible using O(1)
> memory.
I have the same intuition, although I don't care enough to code it up
work out the details.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 1/31/2012 8:43, Kevin Wampler wrote:
> I have the same intuition, although I don't care enough to code it up work
> out the details.
I tried that on math tests a couple times. It didn't fly. :-)
--
Darren New, San Diego CA, USA (PST)
People tell me I am the counter-example.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 02/02/2012 03:07 AM, Darren New wrote:
> On 1/31/2012 8:43, Kevin Wampler wrote:
>> I have the same intuition, although I don't care enough to code it up
>> work out the details.
>
> I tried that on math tests a couple times. It didn't fly. :-)
Huh. It worked for Pierre de Fermat. :-P
But I have to say I'm relieved. Sometimes I worry that education has
sunk to the level where that kind of thing might be OK. Like when I paid
for university tuition only to have some professor of computer science
tell me that "float supports numbers up to about 2^38 which is, oh, far
more than the number of atoms in the entire universe".
(Pro tip: Number of atoms in 12g of carbon = 2^77 or so. The number of
atoms in the /entire universe/ is clearly much, much larger.)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
