Tag: algorithm

计算剩余时间: 什么是一个好的algorithm来确定剩下的时间来完成一些事情？我知道总共有多less条线路，已经有多less条线路了，我应该如何估算剩余的时间？

空algorithmO（0）的时间复杂度是多less？: 所以给了以下程序：这个程序的时间复杂度是O（0）吗？换句话说，是0 O（0）？我想在另外一个问题上回答这个问题会让我们看到这个问题。编辑：很多好的答案在这里！我们都同意0是O（1）。问题是，也是0 O（0）？

O（n！）的例子？: O（n！）函数的例子（在代码中）是什么？它应该采取适当数量的操作来参照n来运行; 也就是说，我在问时间的复杂性。

如何检查一个整数是3的幂？: 我看到这个问题，并popup这个想法。

`std :: list <> :: sort（）` – 为什么突然切换到自顶向下的策略？: 我记得自从时代开始以来，实现std::list<>::sort()的最stream行的方法是以自底向上的方式实现的经典合并sortingalgorithm（另请参阅什么使得gcc std :: listsorting实现如此之快？）。我记得有人把这个策略恰当地称为“洋葱链”的方法。至less在GCC的C ++标准库实现中就是这样的（例如，请参阅这里）。而这正是MSVC版本标准库中老版本Dimkumware的STL以及MSVC所有版本VS2013的所有版本。然而，随VS2015提供的标准库突然不再遵循这种分类策略。 VS2015附带的库使用相当简单的recursion实现自顶向下合并sorting。这让我觉得很奇怪，因为自上而下的方法需要访问列表的中点，以便将其分成两半。由于std::list<>不支持随机访问，所以find中点的唯一方法是从字面上遍历列表的一半。另外，最初需要知道列表中元素的总数（在C ++ 11之前不一定是O（1）操作）。不过，VS2015中的std::list<>::sort()正是这样做的。下面是该实现的摘录，它定位中点并执行recursion调用 … iterator _Mid = _STD next(_First, _Size / 2); _First = _Sort(_First, _Mid, _Pred, _Size / 2); _Mid = _Sort(_Mid, _Last, _Pred, _Size – _Size / 2); … 正如你所看到的，他们只是无情地使用std::next来遍历列表的前半部分，并到达_Mid迭代器。我想知道这个开关背后的原因是什么？我所看到的是在recursion的每个级别重复调用std::next看似明显的低效率。天真的逻辑说，这是慢的。如果他们愿意支付这种价格，他们可能期望得到回报。他们到底是什么？我不会立即看到这种algorithm具有更好的caching行为（与原始的自底向上方法相比）。 […]

set和unordered_set在C ++中有什么区别？: 遇到这个很好的问题，这是相似的，但由于它具有不同的哈希表的实现，因为它具有同步的访问器/ mutators HashMap和Hashtable之间的差异，因为它谈论Java是相似的但是完全不一样？那么set和unordered_set的C ++实现有什么区别呢？这个问题可以扩展到map vs unordered_map等其他C ++容器。这是我的初步评估 set ：虽然标准并没有明确地要求它被实现为树，但是时间复杂性约束被要求为find / insert操作，意味着它总是被实现为树。通常作为高度平衡的RB树（如在GCC 4.8中所见）。由于它们是高度平衡的，它们对于find（）具有可预测的时间复杂度，优点：紧凑（与其他DS相比） Con：访问时间复杂度是O（lg n） unordered_set ：虽然标准没有明确地要求它被实现为树，但是时间复杂性约束要求它的查找/插入操作，意味着它总是被实现为散列表。优点：更快（承诺O（1）分期付款）与树DS相比，易于将基本原语转换为线程安全的缺点：查找不保证是O（1）最坏的情况是O（n）不像树那么紧凑。（为了实际的目的，加载因子从不是1）注意：散列表的O（1）来自于没有碰撞的假设。即使使用0.5的载荷系数，每第二次可变插入也会导致碰撞。可以观察到，哈希表的负载因子与访问其中的元素所需的操作的数量成反比。更多的我们减less#operations，更稀疏的哈希表。当存储的元素的大小与指针相当时，开销是非常重要的。编辑：由于大多数人说的问题包含了足够的答案，所以我将这个问题改为“我错过了地图/设置性能分析之间的任何区别，应该知道的区别？

如何find一串括号，大括号和方括号的有效性？: 我最近接触到这个有趣的问题。给你一个只包含字符'(' ， ')' ， '{' ， '}' ， '['和']'的string，例如"[{()}]" ，你需要写一个函数会检查这个inputstring的有效性，函数可能是这样的： bool isValid(char* s); 这些括号必须以正确的顺序closures，例如"()"和"()[]{}"都是有效的，但是"(]" ， "([)]"和"{{{{"不是！我出来以下O（n）时间和O（n）空间复杂性解决scheme，它工作正常：保持一堆字符。每当你发现开放大括号'(' ， '{'或'['推到堆栈上。每当你发现右括号')' ， '}'或']' ，检查堆栈顶部是否对应的左括号，如果是，则popup堆栈，否则打破循环并返回false。重复步骤2 – 3，直到string结束。这个工作，但我们可以优化它的空间，可能是恒定的额外空间，我明白，时间复杂性不能小于O（n），因为我们必须看每一个字符。所以我的问题是我们可以在O（1）空间中解决这个问题吗？

基数sorting与计数sorting与桶sorting。有什么不同？: 我正在阅读基数，计数和桶sorting的定义，似乎所有这些都只是下面的代码： public static void sort(int[] a, int maxVal){ int [] bucket=new int[maxVal+1]; for (int i=0; i<bucket.length; i++){ bucket[i]=0; } for (int i=0; i<a.length; i++){ bucket[a[i]]++; } int outPos=0; for (int i=0; i<bucket.length; i++){ for (int j=0; j<bucket[i]; j++){ a[outPos++]=i; } } } 我知道我不能对，所以我错过了什么？如果您认为可以帮助解释Java或C语言，请显示代码

塔之间收集水: 最近我遇到了亚马逊问的一个面试问题，我无法find一个优化的algorithm来解决这个问题：您将得到一个input数组，其中每个元素表示一个线塔的高度。每个塔的宽度是1.开始下雨。塔楼之间收集了多less水？例 Input: [1,5,3,7,2] , Output: 2 units Explanation: 2 units of water collected between towers of height 5 and 7 * * *w* *w* *** **** ***** 另一个例子 Input: [5,3,7,2,6,4,5,9,1,2] , Output: 14 units Explanation= 2 units of water collected between towers of height 5 and 7 + 4 units of […]

后缀数组algorithm: 在阅读了一段时间之后，我已经想出了一个后缀数组和LCP数组代表了什么。后缀数组：表示数组中每个后缀的_lexicographic等级。 LCP数组：包含两个连续后缀之间的最大长度前缀匹配，按照字典顺序sorting 。我已经努力了解了几天，后缀数组和LCPalgorithm的工作原理。这是从Codeforces获取的代码： /* Suffix array O(n lg^2 n) LCP table O(n) */ #include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define REP(i, n) for (int i = 0; i < (int)(n); ++i) namespace SuffixArray { const int MAXN = 1 << 21; char * S; int […]