概率算法与搜索有序表：O(n)时间复杂度解析

"此资源为中国科技大学的一份关于概率算法的PPT，主要讲解了时间复杂度为O(n)的确定算法以及概率算法的基本概念和应用。PPT中以寻找宝藏的故事为例，阐述了在某些情况下概率算法优于确定性算法的策略。" 在计算机科学中，算法的设计和分析至关重要，特别是在处理大规模数据时。本PPT聚焦于时间复杂度为O(n)的确定算法，这是算法效率的一个重要衡量标准，表示算法在最坏情况下的运行时间与输入规模成正比。PPT中提到的`Search(x, i)`算法是在已排序的表中查找元素x的线性搜索方法，其时间复杂度正是O(n)。当从位置i开始，如果x大于当前值`val[i]`，则会移动到下一个指针`ptr[i]`，直到找到等于x的元素或遍历完整个表。`A(x)`函数是这个搜索过程的入口，它从头开始（位置head）进行搜索。 概率算法是算法设计的一个分支，它允许在决策过程中引入随机性，以期在预期上提高性能。PPT中的故事解释了概率算法的优势：在寻找宝藏的例子中，面对可能的风险，随机选择有时可以带来更好的结果，因为它避免了过度计算的时间成本。故事中的“方案3”就是一种概率算法，通过掷硬币决定行动路径，虽然可能会遭受最坏的情况，但平均赢利期望值更高。 概率算法的期望时间和平均时间是衡量其性能的关键指标。确定算法的平均执行时间是指在所有输入实例等概率出现的情况下，算法的平均运行时间。而概率算法的期望执行时间则分为两种：一是所有输入实例上的平均期望执行时间，二是最坏输入实例上的期望执行时间。例如，快速排序中的随机划分就是一个典型概率算法的应用，随机选择基准元素可以使得算法在大多数情况下表现得更快。 这份PPT强调了在特定场景下，适当利用随机性可以提高算法的效率，尤其是在时间复杂度受限的情况下。概率算法不仅在理论上具有优势，而且在实践中，如数据库查询优化、网络路由和机器学习等领域都有广泛应用。