For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them?
I used to calculate the maximum (worst) count of basic (most costing) operation in the algorithm.
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Not an answer to your question, but given your interest in this kind of thing, you might also be interested in cs.stackexchange.com/q/13669/755 $\endgroup$– D.W. ♦May 2, 2015 at 1:28
-
1$\begingroup$ "complexity of an algorithm" when referring to asymptotic runime is a (frequently used) misnomer. You want to say "asymptotic runtime". $\endgroup$– Raphael ♦May 4, 2015 at 18:20
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
Computational complexity is just a more general term, as time is not the only resource we might want to consider. The next most obvious is the space that an algorithm uses, and hence we can talk about space complexity, also as a part of computational complexity. Indeed we can do this for any measure you care you use, of course some measures are more useful than others.
So counting the number of steps that an algorithm takes in the worst case gives a time complexity bound for the problem it solves, counting how much memory/how many tape cells it uses gives a space complexity bound etc. etc.
Remember also that if you want to be strict, complexity refers to the problem, not the algorithm, so a problem has complexity bounds, an algorithm has resource bounds (running time, space use...). It's just a matter of definitional formality, complexity theory deals with problems. Yes, algorithms are a key tool for analysing problems and complexity and algorithmics are closely tied together, but formally we wouldn't say Merge-Sort (an algorithm) is in $P$, it's the problem $\mathsf{Sorting}$ which is in $P$. Merge-Sort uses certain resources ($O(n\log n)$ steps for example). The resource bound and correctness of the algorithm imply the complexity (upper) bound for the problem, but they're different things. $\mathsf{Sorting}$ is also $TC^{0}$-complete under $AC^{0}$-reductions, this complexity bound can only really be stated for a problem (but does have algorithmic implications).
answered May 2, 2015 at 1:16
-
$\begingroup$ @shekharsuman By problem I mean the formal notion of a computational problem (e.g. k-Vertex Cover), not the general meaning. Computational complexity is the classification of computational problems, so in a formal sense, the complexity refers to what we can say about the problem. The results about algorithms tell us things about the complexity of problems, but are not in and of themselves complexity results (but informally we do talk about the complexity of an algorithm). $\endgroup$ May 2, 2015 at 7:55
-
1$\begingroup$ @shekharsuman the opening paragraph of the wikipedia page is a pretty good summary. $\endgroup$ May 2, 2015 at 8:21
-
$\begingroup$ @Luke Thanks, this makes things clear. However, if I can use the idiom "most used type of complexity to formally evaluate algorithms" (Even though I know this is not precise). What would it be time vs. computational? What I think is that, in general, the most important thing is time, as resources are more extensible in some sense! $\endgroup$ May 2, 2015 at 9:45
-
1$\begingroup$ @MedianHilal time is indeed the most commonly considered measure for the complexity of a problem. Space is not too far behind (at least by complexity theorists, and people dealing with very large datasets, less so day-to-day). $\endgroup$ May 2, 2015 at 13:14
$\begingroup$
$\endgroup$
8
Cyclomatic complexity is often used as the measure of computational complexity a useful example is provided in https://stackoverflow.com/questions/9097987/calculation-of-cyclomatic-complexity
There may be many different (possibly nested) paths through an algorithm giving it a high cyclomatic complexity, but no loops giving it a low time complexity. A program with a single loop would have a low cyclomatic complexity but possibly a high time complexity.
Cyclomatic complexity is often used as a measure of the maintenance required for the code. A more detailed discussion is provided in http://docs.sonarqube.org/display/SONAR/Bad+Distribution+of+Complexity. This is different to time complexity that is run time measurement of the code and may be used to assess the users perception of the effectiveness of the system.
-
$\begingroup$ The question is about computational-complexity,not about cyclomatic complexity! $\endgroup$ May 2, 2015 at 7:10
-
$\begingroup$ You may want to read the OP - he's asking about the complexity of an algorithm - Cyclomatic complexity gives a static measure of an algorithms computational complexity - try adding positive feedback next time $\endgroup$ May 2, 2015 at 7:44
-
2$\begingroup$ Cyclomatic complexity does not measure computational complexity. Computational complexity refers to running time, not how complex the source code structure is. $\endgroup$– D.W. ♦May 2, 2015 at 7:45
-
$\begingroup$ @D.W. More accurately, computational complexity refers to resources required to solve a problem (which might include space, alternation, oracle calls and so on, as well as time). $\endgroup$ May 2, 2015 at 9:24
-
$\begingroup$ @DavidRicherby I am no expert on this, so please correct if wrong. Static complexity measures, such as program size do play a role in some situation. Am I correct that it is more related to Kolmogorov complexity. Would that t be also the case for Cyclomatic complexity? One kind of complexity for writing programs or problems, and the other for solving or running them ... possibly a brief approximation of the situation. I am not sure I would write a sensible question on this. $\endgroup$– babouMay 2, 2015 at 9:37