4.例子 ①快速排序中的随机划分 要求学生写一算法,由老师给出输入实例,按运行时间打分, 大部分学生均不敢用简单的划分,运行时间在1500-2600ms, 个学生用概率的方法划分,运行时间平均为300ms ②8皇后问题 系统的方法放置皇后(回溯法)较合适,找出所有92个解0(2 若只找92个其中的任何一个解可在线性时间内完成On) 随机法:随机地放置若干皇后能够改进回溯法,特别是当n较大 时 ③判断大整数是否为素数 确定算法无法在可行的时间内判断一个数百位十进制数是否素 数,否则密码就不安全。 概率算法将有所作为:若能接受一个任意小的错误的概率8 4. 例子 ① 快速排序中的随机划分 要求学生写一算法，由老师给出输入实例，按运行时间打分， 大部分学生均不敢用简单的划分，运行时间在1500-2600ms， 三个学生用概率的方法划分，运行时间平均为300ms。 ② 8皇后问题 系统的方法放置皇后(回溯法)较合适，找出所有92个解 O(2 n)， 若只找92个其中的任何一个解可在线性时间内完成O(n)。 随机法：随机地放置若干皇后能够改进回溯法，特别是当n较大 时 ③ 判断大整数是否为素数 确定算法无法在可行的时间内判断一个数百位十进制数是否素 数，否则密码就不安全。 概率算法将有所作为：若能接受一个任意小的错误的概率