算法 | CS笔记

算法

小学数学中的竖式计算，就是一个算法，曾被用于设计乘法电路......小到Sorting或Searching，大到AI，算法统治着一切！

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. Sometimes, different data structure would cause different asymptotic performance of algorithm.

Facts

任何基于比较的搜索算法都有\(\Omega(\log{n})\)。任何基于比较的排序算法都有\(\Omega(n\log{n})\)。这两个Theorem都可用Decision Tree Model证明。

证明某个问题属于NPC，建议放弃寻找最优的快速算法...

Proof of the Halting Problem

def halt(func, *args, **kwargs) -> bool:
    """ Return True if func(args,kwargs) would stop, otherwist False. """
    ...  # ??

def magic(*args, **kwargs):
    while halt(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》

Subproblems

Divide&Conquer算法思路非常的自然和普遍，将大问题分解成Subproblem，逐个击破，而小问题的时间复杂度为通常是\(\Theta(1)\)。

MergeSort的Divide总是平衡的，所以快。平衡就意味着用最少的Conquer（recursive call）层数，就能到达Base。有些算法的worst case，就来自于极不平衡的divide（可能是input造成的）。虽然不平衡的divide，也可以用\(\Theta(\log{n})\)来统一概括复杂度，但越不平衡，Hidden Constant就越大。（学术研究一般忽略Hidden Constant，但实际编程还是需要考虑的）

如果Subproblem之间存在Overlap，避免重复计算也是正常思路，这就引出了Dynamic Programming！或者Subproblem之间存在一些可以被利用的关联，进一步提高算法性能。

Dynamic Programming被普遍应用于Optimization问题，问题本身具有Optimal Substructure特性，常常是在一堆候选组合中选择最优的。

Greedy有点特殊，有些问题在划分Subproblem后，可以直接做出最优选择，而不必等待Subproblem的计算结果。此时也可以使用Dynamic Programming，但性能不够好。

-- 目录[6] --

-- 文章[20] --