《算法技术手册》一2.3.1 最坏情况

简介: 本节书摘来华章计算机《算法技术手册》一书中的第2章 ,第2.3.1节, George T.Heineman Gary Pollice Stanley Selkow 著 杨晨 曹如进 译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.3.1 最坏情况

对于任一特定值n,算法或者程序在处理所有规模为n的样本时的执行时间可能会发生巨大的变化。对于一个给定的程序和一个给定的值,最坏的执行时间就是处理所有规模为n的数据所需要的最长执行时间。
之所以关注算法的最坏情况,是因为它通常是最容易分析的情况。此外,它还能够说明程序在各种场景下到底会有多慢。
更正式地说,如果Sn是所有规模为n的问题样本si构成的集合,t()代表算法对于每一个问题样本所需要的执行时间,那么算法在最坏情况下的执行时间为:t(si)对于所有si∈Sn的最大值。我们将Sn在最坏情况下的性能记作Twc(n)。Twc(n)的增长率定义了算法在最坏情况下的复杂度。
一般来说,通过计算每一份数据si来判定算法在哪份数据上表现最坏,这种做法是不切实际的——没有足够的资源。相反,算法分析人员会精心设计出能让算法的性能落入最坏情况的问题样本。

相关文章
|
20天前
|
机器学习/深度学习 人工智能 自然语言处理
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-19
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-19
43 2
|
20天前
|
机器学习/深度学习 人工智能 自然语言处理
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-16
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-16
24 1
|
20天前
|
机器学习/深度学习 人工智能 算法
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-15
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-15
43 1
|
20天前
|
机器学习/深度学习 人工智能 自然语言处理
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-14
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-14
29 1
|
20天前
|
存储 人工智能 算法
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-18
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-18
33 0
|
20天前
|
机器学习/深度学习 人工智能 自然语言处理
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-17
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-17
54 0
|
20天前
|
存储 机器学习/深度学习 人工智能
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-13(下)
计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-10-13(下)
43 0
|
15天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
2天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。