 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I was reading a description for a computer algorithm. Get this, the
authors claim that the time-complexity is proportional to the "inverse
Ackermann function".
That's a good thing, right? I mean, the Ackermann function grows
absurdly fast, so its inverse presumably grows absurdly slowly.
(Quite how any algorithm's run-time could ever be proportional to
something as obscure and arbitrarily defined as the inverse of the
Ackermann function, I have no idea... I guess now I've seen everything.)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 6/4/2012 2:12 PM, Orchid Win7 v1 wrote:
> I was reading a description for a computer algorithm. Get this, the
> authors claim that the time-complexity is proportional to the "inverse
> Ackermann function".
Union-find structures I assume?
> (Quite how any algorithm's run-time could ever be proportional to
> something as obscure and arbitrarily defined as the inverse of the
> Ackermann function, I have no idea... I guess now I've seen everything.)
You could of course look a proof and read through it.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 04/06/2012 10:25 PM, Kevin Wampler wrote:
> On 6/4/2012 2:12 PM, Orchid Win7 v1 wrote:
>> I was reading a description for a computer algorithm. Get this, the
>> authors claim that the time-complexity is proportional to the "inverse
>> Ackermann function".
>
> Union-find structures I assume?
Actually, something much more complicated than that.
> You could of course look a proof and read through it.
I saw the proof. It's about 20 pages of dense formulas. Clearly I'd need
to study it very carefully to figure out what the hell is going on...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 6/5/2012 12:34 AM, Orchid Win7 v1 wrote:
> On 04/06/2012 10:25 PM, Kevin Wampler wrote:
>> On 6/4/2012 2:12 PM, Orchid Win7 v1 wrote:
>>> I was reading a description for a computer algorithm. Get this, the
>>> authors claim that the time-complexity is proportional to the "inverse
>>> Ackermann function".
>>
>> Union-find structures I assume?
>
> Actually, something much more complicated than that.
Intersting, what was it, I'm curious? The only other algorithm with
that complexity I can think of off the top of my head is an MST algorithm.
In that case, however, you may be further interested to know that the
standard union-find algorithm also has inverse Acermann complexity.
Thus there's an even simpler example of something with that "odd"
complexity.
>
>> You could of course look a proof and read through it.
>
> I saw the proof. It's about 20 pages of dense formulas. Clearly I'd need
> to study it very carefully to figure out what the hell is going on...
Yeah, that proof does suck a little like that.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> Union-find structures I assume?
>>
>> Actually, something much more complicated than that.
>
> Intersting, what was it, I'm curious? The only other algorithm with that
> complexity I can think of off the top of my head is an MST algorithm.
An optimisation algorithm for logic programming.
> In that case, however, you may be further interested to know that the
> standard union-find algorithm also has inverse Acermann complexity. Thus
> there's an even simpler example of something with that "odd" complexity.
That's really odd. The Ackermann function is an ad hoc function with
arbitrarily-chosen coefficients which was thrown together to prove a
point. Why it should /ever/ occur in real life is beyond me...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Am 06.06.2012 09:57, schrieb Invisible:
>>>> Union-find structures I assume?
>>>
>>> Actually, something much more complicated than that.
>>
>> Intersting, what was it, I'm curious? The only other algorithm with that
>> complexity I can think of off the top of my head is an MST algorithm.
>
> An optimisation algorithm for logic programming.
>
>> In that case, however, you may be further interested to know that the
>> standard union-find algorithm also has inverse Acermann complexity. Thus
>> there's an even simpler example of something with that "odd" complexity.
>
> That's really odd. The Ackermann function is an ad hoc function with
> arbitrarily-chosen coefficients which was thrown together to prove a
> point. Why it should /ever/ occur in real life is beyond me...
function" (which is probably the case), then I see nothing
"arbitrarily-chosen" in its recursive definition.
Maybe the Ackermann function you know is a different one? According to
Wikipedia, "'the Ackermann function' may refer to any of numerous
variants of the original function", modified "to suit various purposes".
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
