Timeline for How to describe algorithms, prove and analyse them?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| May 2, 2016 at 18:43 | history | edited | Raphael | CC BY-SA 3.0 |
added 42 characters in body
|
| Apr 1, 2014 at 15:44 | history | edited | Raphael | CC BY-SA 3.0 |
makes source link more robust
|
| Jun 18, 2012 at 14:00 | history | edited | Raphael | CC BY-SA 3.0 |
adds proof outline for section three
|
| Jun 17, 2012 at 12:48 | comment | added | Raphael | @FrankScience: I'm not sure what your question is, then. If you want to count operations precisely, you need to use low-level algorithm statement and analysis. Regarding your other comment, I will edit in the key points of the proof. In the meantime, feel free to try and tackle the recursion with elementary mathematics; I don't know how to do that. Note that $n=2^k$ is no longer assumed. | |
| Jun 17, 2012 at 12:15 | comment | added | Yai0Phah | Yes, ignoring caching and so on. My question is stated not only for $T(n)$ but also for count some operations. In Knuth's viewpoint, he uses flow chart and Kirchoff's first law, which is easier to check whether the count is right or wrong, but pseudo code is not. I find that pseudo code is easier for us to count roughly (for example, $A \sim m+n$ where $A$ is the times of some operation), but exactly, it's easier to forget something, perhaps $\pm1$. Incidentally, where have you used dgf? | |
| Jun 17, 2012 at 12:08 | comment | added | Raphael | @FrankScience: In order to get close to practice, you would have to count all operations (like Knuth does). Then, you can instantiate your result with machine-specific operation costs to get real runtime (ignoring effects the order of operations might have, caching, pipelines, ...). Usually, people only count some operations, and in that case fixing $\alpha$ and $\beta$ does not tell you much. | |
| Jun 17, 2012 at 12:04 | comment | added | Yai0Phah | @JeffE for example, the MIX/MMIX in taocp is, but it's too hard to translate an algorithm to such a machine language. | |
| Jun 17, 2012 at 12:02 | comment | added | Yai0Phah | @JeffE I have to claim that, the $\alpha$ and $\beta$ should only be exact enough to do some comparison. More briefly, a mathematical model which can do a lot of works, without machine languages, to determine the constants. | |
| Jun 17, 2012 at 11:34 | comment | added | JeffE | @Frank: The short answer is You can't; the constants depend on implementation details—including the machine architecture, language, and compiler—that are immaterial to the underlying algorithm. | |
| Jun 17, 2012 at 3:33 | comment | added | Yai0Phah | My question of running-time-analysis is that, how to determine $\alpha$ and $\beta$ exactly $T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+\alpha n+\beta$, which is close to practice (e.g, it's availabe to compare merge-sort and qsort). | |
| Jun 17, 2012 at 3:28 | vote | accept | Yai0Phah | ||
| Jun 16, 2012 at 14:10 | history | answered | Raphael | CC BY-SA 3.0 |