学科分类 - 《中国大百科全书》第三版网络版

高级搜索

个人中心
机构中心
退出

专业板块专题板块大众板块

首页 . 理学 . 计算机科学技术

算法分析/ analysis of algorithms // analysis of algorithms /

计算机科学领域的核心之一，主要是用数学工具为手段，分析各种算法的理论复杂度（包括时间、空间等）和证明算法的正确性，并因此指导人们设计更好的算法。

最坏情况分析/ worst case analysis /worst case analysis
算法分析
算法分析是指分析算法运行所需要的各种资源的数量。所谓最坏情况分析是指分析算法在最坏情况下所需的各种资源的数量，也就是对所有大小为L的输入，算法所需的最多的资源数量。通常分析算法所需要的时间和空间的数量。由此，最坏情况下的时间复杂性就是指对所有大小为L的输入算法所需的最多的基本运算的步骤数；最坏情况下的空间复杂性就是指对所有大小为L的输入算法所需的（除输入外）最多的基本存储单元的个数。
平滑分析/ smoothed analysis /smoothed analysis
算法分析
相对较新的一种算法分析方法。是D.斯皮尔曼（Daniel Spielman）和滕尚华（Shang-Hua Teng）于2001年提出的。
平摊分析/ amortized analysis /amortized analysis
算法分析
一种算法分析方法。
平均情况分析/ average case analysis /average case analysis
算法分析
算法分析是指分析算法运行所需要的各种资源的数量。所谓平均情况分析（average case analysis）是指分析算法平均所需的各种资源的数量，也就是对所有大小为L的输入，算法所需资源的平均数量。人们通常分析算法所需要的时间和空间的数量。从而，平均情况下的时间复杂性就是指对所有大小为L的输入算法所需的基本运算的步骤数的平均数；平均情况下的空间复杂性就是指对所有大小为L的输入算法所需的（除输入外）基本存贮单元个数的平均数。
算法下界分析/ algorithm lower bound analysis /algorithm lower bound analysis
算法分析
在近似算法的设计与分析中，近似性能比的分析有时并不紧（tight），即分析得到的近似性能比并不是所设计算法的严格下界，为此需要对算法的下界进行分析。

算法分析/ analysis of algorithms // analysis of algorithms /

最坏情况分析/ worst case analysis /worst case analysis

平滑分析/ smoothed analysis /smoothed analysis

平摊分析/ amortized analysis /amortized analysis

平均情况分析/ average case analysis /average case analysis

算法下界分析/ algorithm lower bound analysis /algorithm lower bound analysis