Tag: big o

Math.Sqrt（）的时间复杂度？: 我怎样才能找到这个function的复杂性？ private double EuclideanDistance(MFCC.MFCCFrame vec1, MFCC.MFCCFrame vec2) { double Distance = 0.0; for (int K = 0; K < 13; K++) Distance += (vec1.Features[K] – vec2.Features[K]) * (vec1.Features[K] – vec2.Features[K]); return Math.Sqrt(Distance); } 我知道下面的部分是O（1）： double Distance = 0.0; for (int K = 0; K < 13; K++) Distance += (vec1.Features[K]-vec2.Features[K])*(vec1.Features[K]-vec2.Features[K]); 但我无法弄清楚Math.Sqrt()的复杂性是什么。

如何解决素数函数的Big-O表示法？: 我想了解Big-O表示法。很抱歉，如果我问的是太明显的东西，但我似乎无法解决这个问题。我有以下C＃代码函数，我正在尝试计算Big-O表示法。 for (i = 2; i < 100; i++) { for (j = 2; j (i / j)) Console.WriteLine(“{0} is prime”, i); } 到目前为止我得到的是，我认为if子句被认为是常数O（1）并且在计算此算法时没有考虑到这一点？如果我已经正确理解了一个for循环 for(i = 0; i < 100; i++) 因为它是线性函数，所以O（n）和嵌套循环不依赖于来自周围循环的变量 for(i = 0; i < 100; i++) for(j = 0; j < 100; j++) 是O（n ^ 2）？但是我如何计算一个函数，例如第二个循环依赖于第一个循环并创建非线性函数的顶部函数？我发现了一个linearithmic的定义线性算法可以扩展到巨大的问题。 […]

Big O是一个嵌套的for循环，里面有Any（）会是什么？: 这个问题基本上是我在这里回答的后续问题。我真的想说这个算法的Big-O是什么，但我不确定我的说法是完全合理的。所以给出了两个数组： B = [ “Hello World!”, “Hello Stack Overflow!”, “Foo Bar!”, “Food is nice…”, “Hej” ] A = [ “World”, “Foo” ] 什么是大O： List results = new List(); foreach (string test in B) { if (A.Any(a => test.Contains(a)) results.Add(test); } 我相信它介于O(n)和O(n^2)因为它取决于结果中Any()匹配的位置……

ContainsKey和TryGetValue的性能是什么？: 我正在准备采访，一些明显的采访问题，如计算字符串中字符的频率，涉及将所有字符放入Hashtable / Dictionary中，以便获得算法的O（n）运行时间。我的问题是，使用ContainsKey和TryGetValue检查是否已将某个密钥插入Hashtable会导致性能下降？对于使用ContainsKey或TryGetValue问题，我是否仍然可以使用O（n）算法？

Linq OrderBy（）。ThenBy（）方法序列的时间复杂度是多少？: 我在我的项目中使用Linq和Lambda Operations，我需要根据类的两个属性对List进行排序。因此，我使用了OrderBy（）。ThenBy（）方法如下： class ValueWithIndex{ public long Value; public int Index; } … List valuesWithIndex = new List(); for (int i = 0; i v.Value).ThenBy(v => v.Index); … 在本回答中，解释了OrderBy（）使用Quicksort，因此即使它具有O（N * logN）平均时间复杂度，对于最坏的情况，时间复杂度约为O（N 2 ）。如果ThenBy（）方法的时间复杂度最差为O（N 2 ），那么使用这些方法毫无意义。 ThenBy（）方法也使用Quicksort吗？如果是，那是否意味着对于相同的“v.Value”，“v.Index”会被排序为O（N 2 ）最差的时间复杂度？

为什么HashSet 类不用于实现Enumerable.Distinct: 我需要以大O表示法访问IEnumerable.Distinct的渐近时间和空间复杂度所以我在看扩展方法Enumerable.Distinct的实现，我看到它是使用和内部类Set ，这几乎是一个带有“开放寻址”的哈希表的经典实现很快引起注意的是Set中的很多代码只是来自HashSet的复制粘贴，有一些遗漏但是，这个简化的Set实现有一些明显的缺陷，例如Resize方法不使用素数作为槽的大小，比如HashSet ，看看HashHelpers.ExpandPrime 所以，我的问题是：这里代码重复的原因是什么，为什么不坚持DRY原则？特别是考虑到这两个类都在同一个程序集System.Core 看起来HashSet会表现得更好，所以我应该避免使用Distinct扩展方法，并编写我自己的扩展方法，使用HashSet而不是Set ？