-
2 votesanswersviews
有向图中循环识别的有效算法？ [重复]
可能重复：用于检测有向图中的循环的最佳算法 我正在寻找一种算法来在有向图中找到循环 . 我的图表只在节点中有标签，而不是在边缘，它可以变得非常大 . 算法的输出应该是作为一组列表的循环，每个列表应该包含循环中涉及的节点的标签，因此，列表中的第一个和最后一个元素应该是相同的 . 我正在使用的图表很可能只有一个连接组件，没有强连接组件 . 预计周期数会很少（我仍然需要检查） . 对于这个或类似的东... -
1 votesanswersviews
对于基于比较的排序的最坏情况，最严格的上限？
有没有办法显示最差的基于比较的排序情况的上限？是不是完全依赖于实现？我可以很好地设计一个代码，将数组的每个元素与每个其他元素进行比较 . 这将是低效的，但它不会是错误的 . 因此，对于最坏情况（即Ω（n log n））的最紧密下限，是否也存在任何最严格的上限？ -
6 votesanswersviews
二元搜索的复杂性
我正在观看Berkley Uni的在线讲座并坚持下面的内容 . Problem ：假设您有一个已经排序的CD集合 . 您要查找 Headers 以"Best Of."开头的CD列表 Solution ：我们将使用二分搜索来查找"Best Of"的第一个案例，然后我们打印直到瓷砖不再"Best Of" Additional question... -
0 votesanswersviews
使用最坏情况，平均情况或摊销分析的公约？
我理解为算法执行复杂性分析的不同情况的机制，但是已经给出了几个场景，并且已经被问到我将针对每种情况使用哪种类型的分析 . 分析类型是“最坏情况”，“平均情况”，“摊销” . 当然要确保算法尽可能高效，我们总是选择使用“最坏情况”？ 我意识到这是主观的，但使用每种分析方法肯定有优点吗？ 这是我在最近的一次面试中给出的4种情景，除了关于飞行员的情况之外，我们无法决定其中的任何情况 . 一家公司发明了... -
-3 votesanswersviews
二进制搜索字符串的复杂性
我有一个排序的字符串数组：例如：[“bar”，“foo”，“top”，“zebra”]我想搜索输入字是否存在于数组中 . 例如： search (String[] str, String word) { // binary search implemented + string comaparison. } 现在二进制搜索将考虑复杂度，即O（logn），其中n是数组的长度 . 所以这么... -
708 votesanswersviews
如何找到算法的时间复杂度
The Question 如何找到算法的时间复杂度？ What have I done before posting a question on SO ? 我经历了this，this和许多其他链接 但是，我没有能够找到关于如何计算时间复杂度的明确而直接的解释 . What do I know ? 比如说下面的代码简单： char h = 'y'; // This will be executed ... -
365 votesanswersviews
持续摊销时间
在讨论算法的时间复杂度时，“恒定摊销时间”是什么意思？ -
271 votesanswersviews
Fibonacci序列的计算复杂性
我理解Big-O表示法，但我不知道如何为许多函数计算它 . 特别是，我一直试图弄清楚Fibonacci序列的幼稚版本的计算复杂性： int Fibonacci(int n) { if (n <= 1) return n; else return Fibonacci(n - 1) + Fibonacci(n - 2); } Fibonacci序... -
0 votesanswersviews
深度优先搜索
在以顶点a开头的图表上执行深度优先搜索 . 遍历邻居时，按字母顺序处理它们 . 问题是找到每个顶点的DFI，Level和Parent . 这是它的图片： 我不确定如何开始这个，这是即将到来的考试的练习题 . 我知道深度优先搜索，它使用一个堆栈，它将从顶点a开始，并在堆栈中按字母顺序排列，但我不知道如何获得每列的值 . 有人可以进一步解释或帮助我吗？ -
0 votesanswersviews
关于空间复杂性的一般混淆
我无法理解空间复杂性 . 我的一般问题是：树上算法的空间复杂度如何小于树中节点的数量？这是一个具体的例子： 如果b是分支因子，则d是最浅目标节点的深度，并且m是状态空间中任何路径的最大长度 对于DFS，空间复杂度应该是O（bm） . 我以为它会一直是树的大小？树的其余部分在哪里？我们如何使用只有O（bm）空间复杂度的整个树？ -
176 votesanswersviews
如何在任何二叉树中找到两个节点的最低共同祖先？
这里的二叉树可能不一定是二进制搜索树 .结构可以视为 - struct node { int data; struct node *left; struct node *right; }; 我可以和朋友一起解决的最大解决方案就是这样 -考虑this binary tree： Binary Tree http://lcm.csa.iisc.ernet.in/dsa/img1... -
16 votesanswersviews
在使用此算法的最坏情况下，二进制搜索会进行多少次比较？
嗨，下面是我的二进制搜索实现的伪代码： Input: (A[0...n-1], K) begin l ← 0; r ← n-1 while l ≤ r do m ← floor((l+r)/2) if K > A[m] then l ← m+1 else if K < A[m] then r ← m-1 else return m ... -
1 votesanswersviews
子集和问题的有趣变化
一位朋友从工作中向我展示了一个有趣的子集和问题变体： 给定S的正整数，大小为n，以及整数a和K，是否存在包含 exactly a elements 的子集R（集合S），其总和等于K？ 他声称这可以用时间复杂度O（nka）来完成，我无法想出一个能够实现这个运行时间的动态编程算法 . 可以吗？ -
0 votesanswersviews
压缩存储2个链表的数组
数组Arr（大小n）可以表示双向链表 . [假设细胞有结构{int val，next，prev; }] 我有两个列表A和B存储在数组中 . A有m个节点，B有n个m个节点 . 这些节点被分散，我想重新排列它们，使得A的所有节点都来自Arr [0] .. Arr [m-1]并且其余由B的节点填充，在O（m）时间内 . 我遇到的解决方案是： 迭代A直到出现超出Arr [m-1]的节点 然后... -
321 votesanswersviews
有没有O（1 / n）算法？
有没有O（1 / n）算法？ 或者其他任何小于O（1）的东西？ -
6 votesanswersviews
为什么在一般情况下，链排序为O（n sqrt n）？
我发现strand sort非常有吸引力，可以在常量空间中对单个链表进行排序，因为它比例如插入排序要快得多 . 我知道为什么它是 O(n) 在最好的情况下（列表已经排序）和 O(n^2) 在最坏的情况下（列表反向排序） . 但为什么 O(n sqrt n) 在平均情况下呢？如果算法不是基于二分法并且具有多项式最佳情况和最差情况性能，那么平均情况是 O(n^m) ，其中 m 是最佳情况的算术平均值'... -
60 votesanswersviews
已知统计分布数据的排序算法？
我刚想到，如果你对要排序的数据的分布（在统计意义上）有所了解，那么如果考虑到这些信息，排序算法的性能可能会受益 . 所以我的问题是，是否有任何排序算法考虑到这种信息？他们有多好？ 编辑：一个示例澄清：如果您知道数据的分布是高斯分布，则可以在处理数据时动态估计平均值和平均值 . 这将为您估算每个数字的最终位置，您可以使用它来将它们放置在最终位置附近 . 编辑＃2：我很惊讶答案不是一个维基链接到一个讨... -
1 votesanswersviews
一些NP-Complete问题怎么也是NP-Hard？
我正在尝试以一种直观的方式将我听到的P，NP，NP-Complete和NP-Hard包裹起来，以便我不必记住他们的定义 . 在下图中（左手方案，P！= NP），NP-Complete和NP-Hard之间存在重叠区域 . 这是否意味着一些问题既是NP-Complete又是NP-Hard？根据这个特殊答案，我发现这是矛盾的：What are the differences between NP, NP... -
1 votesanswersviews
NP-complete与NP-hard（为什么它们不相等？）
为什么NP-hard不等于NP-complete？ My informal understanding of definitions being used: NP - 可以在多项式时间内验证的所有问题 NP完全 - 所有NP和NP难的问题 NP-hard - 至少和NP中最难的问题一样难 决策问题 - 询问有关输入的问题并输出bool值的问题 Confusion: P与NP未知解的问题源于这样... -
0 votesanswersviews
图表回溯复杂性
我试图分析回溯图的复杂性，以便找到最长的路径 . 我的算法包括拓扑排序，然后从每个顶点回溯，以找到最长的路径 . 如果有帮助，算法基本上是：拓扑排序（G），为每个顶点计算彼此顶点的距离，返回最大距离 无论如何，我真的不知道回溯操作的最坏情况复杂性是什么 . 有什么建议？ 提前致谢！ -
17 votesanswersviews
为什么内存中A *指数的复杂性？
维基百科在A *复杂性上说以下（link here）： 比时间复杂度更有问题的是A *的内存使用率 . 在最坏的情况下，它还必须记住指数数量的节点 . 我没有看到这是正确的，因为： 假设我们探索节点A，后继B，C和D.然后我们将B，C和D添加到开放节点列表中，每个节点都附带一个A的引用，我们将A从开放节点移动到关闭节点 . 如果在某个时候我们找到另一条到B的路径（比如通过Q），这比通过A的路径... -
0 votesanswersviews
深度优先搜索示例
我有一个练习考试的深度优先搜索示例，我已经问过另一个关于它的问题，我想我有一些关于它的概念...... 我只是想确认我得到的结果是否正确，如果你可以指导我做错了什么以及如何解决它 . 这是它的图片： http://i.imgur.com/FdKxIUw.png 我从DF到0的顺序得到的结果是： 1 5 7 6 2 3 4 8 9 对于父母，我感到困惑，因为它从0开始，0的父母是4？而4的父母是5？... -
4635 votesanswersviews
什么是“大O”符号的简单英语解释？
我更喜欢尽可能少的正式定义和简单的数学 . -
14 votesanswersviews
如何计算回溯算法的时间复杂度？
如何计算这些回溯算法的时间复杂度，它们是否具有相同的时间复杂度？如果不同怎么样？请详细解释并感谢您的帮助 . 1. Hamiltonian cycle: bool hamCycleUtil(bool graph[V][V], int path[], int pos) { /* base case: If all vertices are included ... -
0 votesanswersviews
回溯算法解决数独难题的时间复杂度
我正在实施一个回溯算法来解决数独谜题，我需要对算法进行实证分析 . 但是，我发现很难理解这种回溯算法的时间复杂度来解决数独谜题 . 数独板是一个9乘9的网格，因此每个空格可以取1-9的值，但它首先检查行，列，3x3框以查看是否安全，并且有m个空格 . 我逐行遍历网格寻找一个空格，然后循环编号1-9，检查哪个数字是安全的 . 如果数字是安全的，我把它放在那里然后再次调用我的函数（重复）来检查下一个空... -
1 votesanswersviews
在定向未加权图中找出最长路径的长度
我有一个有向的，未加权的，可能是循环的图，它可以包含循环和多个重复边（即从节点1到节点2的两条边） . 我现在想在这个图中找到最长路径的长度，即最长路径： - 不使用两次边缘（但如果从节点1到节点2有多个边缘，它可以使用它们中的每一个） - 可能会多次访问节点（即它不必是一个简单的路径） 特别是这个问题NP难吗？我知道最长的简单路径是NP-hard（减少汉密尔顿路径），最长的边缘拒绝路径是P（Be... -
26 votesanswersviews
缺少号码面试问题Redux
确定1到N范围内缺失值的常见访谈问题已经完成了一千次 . 变化包括2个缺失值，最多K个缺失值 . 示例问题：范围[1,10]（1 2 4 5 7 8 9 10）= {3,6} 以下是各种解决方案的示例： Easy interview question got harder: given numbers 1..100, find the missing number(s) 我的问题是，看到一个缺失值... -
25 votesanswersviews
了解Ukkonen的后缀树算法[重复]
这个问题在这里已有答案： Ukkonen's suffix tree algorithm in plain English 6个答案 我正在使用Ukkonen的算法来构建后缀树，但是我不理解作者对其线性时间复杂性的解释的某些部分 . 我已经学会了算法并对其进行了编码，但是我用作信息主要信息源的文章（链接波纹管）在某些部分有点令人困惑，因此对我来说，为什么算法是线性的并不是很清楚 . 有帮助吗？... -
0 votesanswersviews
稀疏矩阵乘法复杂度
我想表达两种算法的计算复杂性：稀疏矩阵稀疏向量乘法和稀疏矩阵稀疏矩阵乘法，如在Eigen或Cusparse中使用CSR表示实现的 . 我知道它取决于几个参数，尤其是每个元素中非零值的数量 . 但是，我无法找到详细说明此类算法复杂性的出版物，并使用O（）表示法表达它 . -
4 votesanswersviews
Theta表示法的简单英文解释？
Theta符号的简单英语解释是什么？尽可能少的正式定义和简单的数学 . theta符号与Big O符号有何不同？谁能用简单的英语解释一下？ 在算法分析中如何使用？我很迷惑？