This... could be painful.
Jul. 22nd, 2008 06:49 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
tcepsaI'm really not supposed to stay up this late on a school night... except dammit, I needed to get the assignment done!
Frakking memoization. The worst part was that my implementation of it was such that the "optimization" actually caused a significantly higher processing time. Stupid graphs and their stupid paths anyway...
But I'm a better programmer for it. Proof that I'm learning in this class: by the time that I wrote the double-nested for loops to ensure that I wasn't letting false positives through, I was starting to suspect that I'd be looking at at least O(n^2) for it. Given that those are happening _inside_ another double-nested set of for loops, that should push the whole time up to, oh, about O(n^4) if I remember right.
SO VERY MUCH LESS THAN IDEAL. Fortunately the memoization part was for extra credit anyway, and I should still be able to score that with a slightly fancier version of the paragraph I just wrote. "I may be taking the Edison approach, but I'm learning! Also, optimization isn't always!"
PS Why am I doing so much algorithm work in a data structures class? ~wry grin~
PPS (Yes I realize that the only good way to appreciate these things is to use them to facilitate the construction of spiffy fast algorithms. And I do. ^_^)
Frakking memoization. The worst part was that my implementation of it was such that the "optimization" actually caused a significantly higher processing time. Stupid graphs and their stupid paths anyway...
But I'm a better programmer for it. Proof that I'm learning in this class: by the time that I wrote the double-nested for loops to ensure that I wasn't letting false positives through, I was starting to suspect that I'd be looking at at least O(n^2) for it. Given that those are happening _inside_ another double-nested set of for loops, that should push the whole time up to, oh, about O(n^4) if I remember right.
SO VERY MUCH LESS THAN IDEAL. Fortunately the memoization part was for extra credit anyway, and I should still be able to score that with a slightly fancier version of the paragraph I just wrote. "I may be taking the Edison approach, but I'm learning! Also, optimization isn't always!"
PS Why am I doing so much algorithm work in a data structures class? ~wry grin~
PPS (Yes I realize that the only good way to appreciate these things is to use them to facilitate the construction of spiffy fast algorithms. And I do. ^_^)
