[Subject Prev][Subject Next][Thread Prev][Thread Next][Subject Index][Thread Index]
Re: "time complexity"
From: Shridhar Daithankar <shridhar_daithankar@xxxxxxxxxx>
I guess it depends upon the algorithm you are using too, unless you are
calculating time complexity of storage and retrieval itself.
Yes, storage and retrieval is the core issue.
I have implemented a solution to knapsack(0/1) problem using dynamic
programming. To prevent unnessary recursive function calls. I've stored the
calls and the corresponding results in a map(I think a "quasi-heap"
implementation). Now I want to know if this is more efficient then a "tuple"
method suggested in a text-book, which uses a list to do the same.
I have to do something with the travelling salesman problem. Due to the
combination of recursion and associative storage, I'm unable to
theoretically approximate the complexity. The flow of the program is not
"simple/predictable".
Even if I know for the complexities of the storage and retrieval algos, (log
n, I think) I cannot work out a correct solution. That's why I need a
program to determin time-complexity.
Somebody spoke about using a graph to approximate the complexity. Is there a
software available for this. Or even this has to be done manually.
I would like to know result of your experiment. My initial guess is that
they
affect the time complexity in a simple predictable way depending upon the
algorithm.
(Looks silly, isn't it?)
Bye
Shridhar
Rajeev Rao wrote:
> If I use a specialised container, such as a map or priority que,
provided by
> the STL, I would like to their impact on the time-complexity. It would
take
> a lot of time to look at the STL implementations, hence a computer doing
the
> job would be nice.
---------------------------------------------
The mailing list archives are available at
http://lists.linux-india.org/cgi-bin/wilma/LIP
_________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.