I'm working (rather beginning) on a Huffman tree. I think I've run in to a problem for time complexity.
Huffman trees are supposed to be fast in most ways.
As I prepare to build my tree, I have three for...next loops in separate methods.
I think that could be very bad time complexity. I think its something like n^3, which isn't just bad its atrocious. n^2 is bad enough. This is only the initialization process that these loops are running at.
One method goes through a 27 length array of FrequentChars (a container class I invented, much like a C struct) and gives each element a new frequentChar, and default values in alphabetical order. The last position (#26) belongs to space characters.
Next I have a findFrequencies() method which goes through the string I'm given, finding where each character occuring belongs and increments the associated frequency inside the freqChars array.
Next I have another loop which places each char and frequency in a priority queue just before building the tree. The Priority Queue and the Tree classes were given to us (I'm taking a class on Advanced data structures and algorithms), and I've modified them to suit my needs. The priorityQueue class can contain Tree elements, and will be used to assemble the tree.
I just feel like this is grossly inefficient. I've been stressed out with other work for some time now, and haven't been able to put much work in to this since it was assigned almost two weeks ago. I'm a fairly proficient programmer, I can make things work, but I don't have much experience making things work well.
I just realized that I have to add yet another for...next loop just to know how big to make my priority queue. The Queue takes a size parameter in its constructor. I could modify the Priority queue class to be dynamic too, but that only just occurred to me.
Am I right about this?
OH and I would provide my code, but it would take up a ton of space and I don't think I can post the instrutors classes without permission.