Complexity
Complexity is an abstract measurer of computational effort and memory usage. This simple definition tells us that the complexity of a algorithm can be break into two part:
- Time complexity
- Space complexity To analyse the time complexity of a algorithm, we usually analyse the order of growth:
- Constant: using the same amount of time no matter the inputs.
- Linear: the time grows linearly with the size of the input.
- Logarithm
- Linearithmic( or log-linear)
- Quadratic: Might be a little annoying starting here.
- Polynomial
- Exponential: We don't want it, it is not scalable at all. A good algorithm should be scalable according to the definition of the algorithm.
The space complexity is similar, and we also use order of growth to analyse it.
Correctness
As a computer scientist, we often want to write a correct algorithms, and correctness is a important part.
First, I should give you the definition of partial correctness.
An algorithm in a state that satisfies a precondition P is partially correct with respect to P and Q if results produced by the algorithm satisfy the postcondition Q. Note that a algorithm is partially correct does not mean that it will give you a correct result. It actually means that if the algorithm produced a result, it will be correct, which implies that this algorithm may not give you a result.
Now we can move forward to** total correctness.** Total correct algorithm is a partially correct algorithm that always gives a result.