大O符号和小o符号的区别
Big-O符号 O(n) 和Little-O符号 o(n) 有什么区别？
扔猫出窗户
假设你和一只猫在高楼里。这只猫可以从低楼层的窗户掉下来而不死，但如果从高楼层扔下去就会死亡。如何通过最少次数的尝试来确定猫能够生存的最大楼层数？ 显然，如果你只有一只猫，那么你只能线性地搜索。先把猫从一楼扔下去。如果它活了下来，再从二楼扔下去。最终，在从第f层扔下后，猫将死亡。你会知道第f-...
把数据作为空值或null值的键存储在HashMap中，这是一个好主意吗？
我最初编写了一个 ArrayList，并将唯一值（用户名，即 Strings）存储其中。后来我需要使用 ArrayList 来搜索其中是否存在用户。这就是搜索所需的 O(n)。 我的技术领导要求我将其更改为 HashMap，并将用户名作为键存储在数组中，将值设为空的 Strings。 因此...
为什么这个算法的大O复杂度是O(n^2)？
我知道这个算法的大O复杂度是O(n^2)，但我不明白为什么。int sum = 0; int i = 1; j = n * n; while (i++ < j--) sum++; 虽然我们一开始设置了j = n * n，但在每次迭代中我们将i增加而将j减少，所以最终的迭代次数应...
我该如何在O(n)时间内在已排序的数组中找到一个出现奇数次的数字？
我有一个问题，思考了很多次却没有想出答案...所以在这里发布这个问题。也许我能得到别人的观点，尝试让它起作用... 问题是：给定一个排序好的数组，其中包含一个出现奇数次数的值和其他出现偶数次数的值。我们需要在log n时间内找到解决方案。 在O（n）时间内找到解决方案很容易，但是在log ...
.NET集合类的渐近复杂度
有没有关于.NET集合类(Dictionary<K,V>, List<T> 等等) 方法渐近复杂度 (大O表示法等) 的相关资源? 我知道C5库的文档包括一些相关信息(例子)，但我也对标准.NET集合类感兴趣...(还有 PowerCollections 的信息也不错)。
Kruskal算法的时间复杂度是多少？
我正在计算Kruskal算法的时间复杂度，方式如下(请参见附图中的算法)。 T(n) = O(1) + O(V) + O(E log E) + O(V log V) = O(E log E) + O(V log V) as |E| >= |V| - 1 T(n) = E lo...
什么是亚线性算法？
我的一位同伴向我提出了以下问题。Which of the following expressions is not sublinear? O(log log n) O(n) O(logn) O(root(n)) 我已经阅读了https://en.wikipedia.org/wiki/Time_...
渐进最优算法：计算一条直线是否与凸多边形相交。
一种检测直线与凸多边形是否相交的O(n)算法是检查多边形的任一边是否与直线相交，并查看相交点数是奇数还是偶数。 是否存在渐进更快的算法，例如O(log n)的算法？
渐近紧密界限（asymptotic tight bound）对于二次函数
在CLRS（由Cormen、Leiserson、Rivest和Stein编写的算法导论）中，对于一个函数 f(n) = an² + bn + c 他们说 假设我们取常数c₁ = a/4，c₂ = 7a/4和n₀ = 2·max(|b|/a, √(|c|/a))。 那么对于所有n ≥ n₀...