Chapter 3 | The Fundamentals: Algorithms¶
Algorithms¶
Definition
An algorithm is a finite set of precise instructions for performing a computation or solving problem.
Pseudocode is instructions given in a generic language similar to a computer language.
Properties
- Input and Output
- Definiteness
- Correctness
- Finiteness
- Effectiveness
- Generality
Complexity¶
Definition
Complexity is the amount of time or space needed to execute the algorithm.
- Space Complexity
- Time Complexity
- Types: best-case time; worst-case time; average-case time.
- P-Class Problem
- P for 「polynomial」
- problems that can be solved by polynomial time algorithm
- NP-Class Problem
- NP for 「nondeterministic polynomial」
- problems for which a solution can be checked in polynomial time
- NP-Complete (NPC) Problem
- If any of these problems can be solved by polynomial worst-case time algorithm, then all can be solved by polynomial worst-case time algorithms.
最后更新:
2023.11.21 17:00:13 CST
创建日期: 2023.01.15 13:54:18 CST
创建日期: 2023.01.15 13:54:18 CST