我已经读过很多次,插入排序具有严格的代码,因此其渐近复杂性中隐藏的常数因子较小。我昨天刚刚读到,快速排序有紧凑的代码,就像插入排序,所以它也有较小的隐藏常数因子。这是在O(n lg n)
排序算法中被认为是最好的原因之一。
当有人说这个算法的代码很紧时,我不明白这意味着什么。这到底意味着什么?它如何提高算法的效率(渐近复杂性中较小的隐藏常数因子)?
发布于 2013-08-30 09:40:56
当一个算法被指定为大O(如O(n log n)
)时,它将告诉您该算法将如何扩展;也就是说,当您将n
的大小增加到一个大的数字时,它的性能将如何。
假设我有一个算法,就是数据集上的O(n)
。这意味着代码中有一个循环在某个地方执行n
次数,对数据集中的每个元素执行一次。执行需要多长时间?假设循环的每一次迭代所需的时间都是相同的,则需要花费的时间。
男*n
其中m是处理数据集中的一个元素所需的时间。
很明显,如果m
更高,处理数据集将需要更长的时间。大O根本不处理这个时间;它只声明(在本例中),该算法将线性地缩放为数据集大小的函数。
因此,“紧循环”只是一个具有较小m
的循环。
这是书中提到的“隐藏不变因素”。减少m
会提高效率,因为m
中的任何改进都将乘以整个数据集。
发布于 2013-08-30 10:00:08
紧密的代码是非常高效的源代码,因为它用最少的资源和没有多余的代码来完成任务。
我想在C#中显示1和3的总和。程序1通过严格的代码来完成这项任务。程序2没有。
方案1:
class Program
{
static void Main(string[] args)
{
Console.Write(4);
}
}
方案2:
class Program
{
static void Main(string[] args)
{
var myAdder = new Adder();
Console.Write(myAdder.GetSum());
}
}
class Adder
{
public Adder()
{
this.FirstOperand = 1;
this.SecondOperand = 3;
}
public int FirstOperand { get; set; }
public int SecondOperand { get; set; }
public int GetSum()
{
return this.FirstOperand + this.SecondOperand;
}
}
https://softwareengineering.stackexchange.com/questions/209999
复制相似问题