算法总结最终版.pdfVIP

• 1：算法描述 • 算法是指解决问题的一种方法或一个过程。 • 算法是若干指令的有穷序列，满足性质： • (1)输入：有外部提供的量作为算法的输入。 • (2)输出：算法产生至少一个量作为输出。 • (3)确定性：组成算法的每条指令是清晰，无歧义的。 • (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 • 算法复杂性 = 算法所需要的计算机资源 • 算法的时间复杂性T(n) ； • 算法的空间复杂性S(n)。 • 其中n是问题的规模（输入大小）。 f(n)= (g(n))的确切意义是：f(n) (g(n))。 理解问题 一般情况下，等式和不等式中的渐近记号 (g(n))表示 (g(n))中的某个函数。 例如：2n2 + 3n + 1 = 2n2 + (n) 表示 精确解或近似解 2n2 +3n +1=2n2 + f(n) ，其中f(n) 是 (n)中某 选择数据结构 个函数。 算法设计策略 等式和不等式中渐近记号O,o, 和 的意义是 类似的。 设计算法 证明正确性 分析算法 设计程序 二分有哪些信誉好的足球投注网站算法复杂度分 析： 2.4大整数的乘法 每执行一次算法的while 循环， 待有哪些信誉好的足球投注网站数组的大 请设计一个有效的算法，可以进行两个n位大整 小减少一半。因此，在 数的乘法运算 最坏情况下，while循环 X = a b 被执行 O(logn) 次。 循环体内运算需要O(1) Y = c d 时间，因此整个算法在 X = a 2n/2 + b Y = c 2n/2 + d 最坏情况下的计算时间 n n/2 复杂性为O(logn) 。 XY = ac 2 + (ad+bc) 2 + bd 复杂度分析  O(1) n1 T(n)  4T(n/ 2) O(n) n1  2 T(n)=O(n ) 没有改进 n n/2 XY = ac 2 + (a