概率型算法思想是允许算法执行某些步骤时，可以随机地选择下一步该如何进行，同时允许结果以较小的概率出现错误，并以此为代价，获得算法允许时间的大幅度较少。随机选择的关键是产生一个随机数用于下一步的选择，此时涉及到随机种子，用于确定随机数的开始点，然后按照某个随机发生器(产生随机数的算法)产生随机数，由于只是一定程度上的随机，应该将随机数称为伪随机数。
1．舍伍德型概率算法：消除算法的时间复杂性与输入实例间的联系，即通过随机选择下一步的执行，使算法的时间复杂度与输入实例的顺序次序无关。如快速排序（随机选择轴元素），选择问题中可以运用。
2．拉斯维加斯概率型算法：随机选择输入看是否能够得到问题的解。随机性的选择可能导致算法陷入僵局，并且算法能够检测是否陷入僵局。它做的随机性选择有可能导致算法找不到问题的解，即算法运行一次，或者得到正确的解，或者无解。因此需要对同一输入实例反复多次运行，直到成功地获得问题的解。可以改进算法的时间性能。典型的应用是八皇后问题，整数因子分解问题。
素数测试方法：判断一个整数n是不是素数，可以通过判断2到根号下n之间的数有没有可以被n的整除的，若没有说明n是素数。
3．蒙特卡洛型概率算法：（常用于true和false问题中）用于问题的准确解。一个蒙特卡洛型概率算法偶尔会出错，但无论任何输入实例，总能以较高的概率找到一个正确解。重复地运行算法，每一次运行都独立的进行随机选择，可以使产生不正确解得概率变得任意小。可以应用在主元素问题中。（主元素是指，数组中的某个元素占数组中的一半以上。）一般求解方法是统计每个元素在数组中出现的次数。蒙特卡洛型概率算法，是随机选择一个元素进行统计，测试是不是主元素，若是时返回，不是时重复测试k次，降低出错的概率。
近似算法：某些问题要求得起最优解时，往往时间代价很大，采用近似算法是用近似最优解代替最优解，以获取算法设计上的简化和时间复杂性的降低。近似比：将最优解和近似最优解两者的比值称为近似比，显然近似比大于1，且近似比接近1时，我们说近似算法能求得较好的近似最优解。
装箱问题可以采用近似算法求解。（装箱问题：设有n个物品和若干个容量为C的箱子，n个物品的体积分别为{s1,s2,…,sn}，如何用最少的箱子数把物品全部装入箱子中。）有方法：首次适宜法，最适宜法，降序首次适宜发和降序最适宜法。
