跳转至

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