学习数据结构与算法的记录
-
欧几里得算法
欧几里得算法解决的是求两个不全为0的非负整数m和n的最大公约数。算法来源于古希腊数学家、亚历山大港的欧几里得所著《几何原本》。欧几里得给出的算法步骤非常简单，但其原理却深刻影响着历代以来的数学家。
欧几里得算法描述：不断重复gcd(m, n)=gcd(n, m mod n)，直至m mod n = 0，因为gcd(m,0)=m，m最终取值也是m和n初值的最大公约数。
-
考虑这样一个问题：如何快速地筛选出不大于给定的数n的所有质数？
埃拉托色尼筛选法给出的方法是：先假设质数序列为2-n，表示2-n中所有数均是质数。依次从序列中取出一个数，然后消除序列中所有它的倍数。当序列中已经没有数字可以消去，仍留在序列中的所有数字就是所要求的不大于n的所有质数。
思考：从直观上，采取这样的方法确实可以快很多，但仍然进行了很多无效的操作，比如6这个数字，在第一次循环时因为2的倍数被消除，但在进行第二次循环时又被3的倍数消除了一次，尽管这里的消除只是直接将值赋值给0，但从算法原理的角度确实需要更多的操作，有没有更好的方法避免这种情况呢？
优化：在筛选2的倍数时，我们是依次筛选2×2,2×3,2×4,2×5...进行3时，按照原本的算法，是筛选3×2,3×3,3×4,3×5...可不可以跳过3×2，直接从3×3开始筛呢？答案是肯定的。规律就是从p×p开始筛。因为可以肯定，开始筛p的倍数时，2×p,3×p...(p-1)×p一定在之前的步骤中消去了。例如筛选p=5时，很容易可以发现2×5,3×5已经分别在筛选2的倍数，3的倍数的过程中筛去，剩下的4×5，可以知道在进行2×10的步骤中消去。这个有点隐蔽，其实想想可以发现，4已经是一个合数，也就是可以拆分为更小的两个数2×2相乘，如果只看其中一个数2，就会发现其实还是在筛选2的倍数。
-
算法思想：从数组[0..n-1]中选择一个最小的数放在第一个位置，再从剩下的[1..n-1]个元素的子数组中选择最小的数放在第二个位置，重复进行n-1步后，算法结束。
时间效率：O(n^2)
-
算法思想：比较数组中相邻的两个元素，如果逆序，则交换它们的位置，重复多次以后，数组中较大的元素总是向着数组末尾“沉”去，数组中较小的元素向首部“浮”去，因此把这种算法叫做“冒泡排序”。
时间效率：O(n^2)
-
算法思想：将数组看成两个子数组，分别是已排序子数组和未排序子数组。初始时，已排序数组中只有第一个元素，未排序数组中是剩下的n-1个元素。依次将未排序数组中的元素插入到已排序数组中合适位置，重复n-1次完成。
时间效率：O(n^2)