建设网站书籍,网站管理是做什么的,怎样下一本wordpress,网站系统说明书【0】README
0.1#xff09; source code and text description are from data structure and alg analysis #xff1b; 【1】分析算法最混乱的方面大概集中在对数上面#xff0c; 除分治算法外#xff0c;可将对数最常出现的规律概括为下列一般法则#xff1a;
1.1 source code and text description are from data structure and alg analysis 【1】分析算法最混乱的方面大概集中在对数上面 除分治算法外可将对数最常出现的规律概括为下列一般法则
1.1如果一个算法用常数时间O(1)将问题的大小削减为其一部分通常是1/2那么该算法就是 OlogN 1.2如果使用常数时间只是把问题减少一个常数如将问题减少1那么这种算法就是 ON 【2】下面我们提供具有对数特点的3个荔枝
Example1二分查找对分查找 注意二分查找的前提是序列已经有序
源代码此算法成立的前提是 MN https://github.com/pacosonTang/dataStructure-algorithmAnalysis/blob/master/chapter2/p22.c 算法分析Analysis A1显然每次迭代在循环内的所有工作花费为O1 因此分析需要确定循环的次数循环从 high-lowN-1开始并在 high-low -1 时结束A2每次循环后high - low 的值至少将该次循环前的值减半于是循环的最多次数为 | log(N-1) |向上取整2A3举个例子若high-low 128则在各次迭代后 high - low 的最大值为 64、32、16、8、4、2、1、0、-1因此运行时间为 OlogN
Example2欧几里得算法——计算两数的最大公因数
两个整数的最大公因数greatest common divisor它是同时整除二者的最大整数如GCD50,155源代码 https://github.com/pacosonTang/dataStructure-algorithmAnalysis/blob/master/chapter2/p23.c 时间复杂度 T(N) O (logN)算法解说Description D1算法通过连续计算余数直到余数为0为止 最后的非零余数就是最大公因数D2可以证明 在两次迭代后余数最多是原始值的一半。这点特别重要D3迭代次数至多是2logNO (logN)引申出一个定理如果 M N , 则 M mod N M / 2 。余数是小于除数N的 记住这一点
Example3幂运算
Attention我们用乘法的次数作为运行时间的度量 源代码 https://github.com/pacosonTang/dataStructure-algorithmAnalysis/blob/master/chapter2/p24.c 时间复杂度 T(N)O (logN) 代码演示分析步骤 算法解说Description D1如计算X^62用到了9次乘法而不是62次乘法 D2显然 所需要的乘法次数最多是 [ 2 * logN向下取整 -1]D3实际上 源代码中的 if(N 1) return x; 不是必须的。为什么自己去想其中的原因去掉后运行结果完全一样
