Algorithm is a procedure of Finite Steps to solve problem in an efficient way hopefully. Take algorithm as a Technology!
Sequence, If...Else..., Loop, and (algorithmic) Recurrence! Recurrence is essentially loop, but more powerful! Loop is for items. Recurrence is for subproblems!
Data structure is used to hold and manipulate data! Using appropriate data structure is an important part of algorithm design.
Theorems
任何基于比较的搜索算法都有\(\Omega(\log{n})\)。任何基于比较的排序算法都有\(\Omega(n\log{n})\)。这两个Theorem都可用Decision Tree Model证明。
Proof of the Halting Problem
defhalt(func,*args,**kwargs)->bool:""" Return True if func(args,kwargs) would stop, otherwist False. """...#defmagic(*args,**kwargs):whilehalt(magic,*args,**kwargs):pass
For the Halting Problem and other unsolvable problems, there are proofs that no algorithm can exist that, for every input, eventually produces the correct answer. A procedure attempting to solve an unsolvable problem might always produce an answer but is sometimes incorrect, or all the answers it produces might be correct but for some inputs it never produces an answer. ---- 《CLRS》
Divide & Conquer:
Base --> Divide --> Conquer --> Combine,Divide and Conquer算法思路非常的自然和普遍,将大问题分解成小问题,逐个击破,而小问题的时间复杂度为通常是\(\Theta(1)\)。
The class P consists of those problems that are solvable in polynomial time.
More specifically, they are problems that can be solved in \(O(N^k)\) time for some
constant k, where N is the size of the input to the problem.
The class NP (Non-deterministic Polynomial) consists of those problems that are verifiable in polynomial time.
\(P\subseteq NP\), but whether \(P=NP\) or not?
NPC stands for NP-complete, which belongs to NP and any NP problem can be reduced to it. If any NPC problem can be solved in polynomial time, then every problem in NP has a polynomial-time algorithm. One should be capable for identifying NPC problem and avoid it by approximation algorithms.
NP-hard might not be a NP, but any NP can reduce to it.