Skip to content

3.Algorithms

Definition

pseudocode:

procedure  max(a1, a2, ..., an :integers)
max := a1
for i := 2 to n
    if max < ai then max:= ai
return max{max is the largest element}

Properties

Input : An algorithm has input values from a specified set.

Output : From each set of input values, an algorithm produces output values from a specified set.

Definiteness : The steps of an algorithm must be defined precisely. （如没有初始化) 

sum := 0//the value of i is not set
while i < 10
sum := sum + i
Correctness : An algorithm should produce the correct output values for each set of input values.

Finiteness : An algorithm should produce the desired output after a finite number of steps for any input in the set.

Effectiveness: Each step of an algorithm must be executed exactly and in a finite amount of time. (关键是每一步) 

procedure divide(n: positive integer)
while n ≥ 0
m := 1/n//can not be executed when n=0
n := n − 1
Generality : The procedure should be applicable for all problems of the desired form, not just for a particular set of input values.

Complexity of Algorithms

Growth of Functions

\(O(g(x))\) is a set of all \(f(x)\) that statisfy \(\existssss C,k,\forall x>k,|f(x)|<C|g(x)|\) Equivalent expression: \(f(x)=O(g(x)), \ f(x)\in O(g(x))\)

\(f(x)=a_nx^n+a_{n-1}x^{n-1}+\dots a_0\), \(f(x)=O(x^n)\)

Proof: \(|f(x)|\leq a_n|x^n|+\dots a_0=|x^n|(a_n+a_{n-1}/x+\dots a_0/x^n) \leq (a_n+\dots a_0)|x^n|(x>1)\)

Take \(C=a_n+\dots a_0,k=1\) as witnesses

\(f_1(x)=O(g_1(x)),f_2(x)=O(g_2(x))\) then \(f_1(x)+f_2(x)=O(\max\{g_1(x),g_2(x)\})\)

\(f_1(x)f_2(x)=O(g_1(x)g_2(x))\)

\(O(a^n)<O(n!)\)

Complexity

Types

  • Worst-case analysis
  • Average-case analysis(Assuming an input probability distribution)
  • Best-case analysis(Not very practical)

Problem types:

  • Tractable: a problem is solvable using polynomial worse-case complexity
  • Intractable
  • Solvable

  • Unsolvable: no algorithm exists(such as the Halting Problem)

  • Class P: tractable problems

  • Class NP: problems for which a solution can be checked in polynomial time
  • NP-Complete:
    • The satisfiablity problem

Comments