-
3 votesanswersviews
找到广场上的所有水坑（算法）
问题定义如下：给你一个正方形 . 广场内衬有1米x 1米的扁平石板 . 草环绕广场 . 石板可能处于不同的高度 . 它开始下雨了 . 确定将创建水坑的位置并计算将包含多少水 . 水不会流过角落 . 在任何草地区域都可以随时浸泡任何体积的水 . 输入： 宽度高度 width * height非负数，描述草地上每个石板的高度 . 输出： 来自水坑的水量 . width * height标志描述将创建水... -
-2 votesanswersviews
图灵机的数量？
你对这个问题有什么看法吗？我不知道它问的是什么 . 具有状态设置（Q-start，Q2，Q3，Q4，Q5，Q6，Q-accept，Q-reject），输入字母（0,1）和磁带字母（0）的图灵机数量是多少？ ，1，x，U）其中U是空白符号？启动，接受和拒绝状态是具有适当名称的状态 . 展示你的作品 . -
4 votesanswersviews
Theta表示法的简单英文解释？
Theta符号的简单英语解释是什么？尽可能少的正式定义和简单的数学 . theta符号与Big O符号有何不同？谁能用简单的英语解释一下？ 在算法分析中如何使用？我很迷惑？ -
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的路径... -
2 votesanswersviews
有向图中循环识别的有效算法？ [重复]
可能重复：用于检测有向图中的循环的最佳算法 我正在寻找一种算法来在有向图中找到循环 . 我的图表只在节点中有标签，而不是在边缘，它可以变得非常大 . 算法的输出应该是作为一组列表的循环，每个列表应该包含循环中涉及的节点的标签，因此，列表中的第一个和最后一个元素应该是相同的 . 我正在使用的图表很可能只有一个连接组件，没有强连接组件 . 预计周期数会很少（我仍然需要检查） . 对于这个或类似的东... -
4 votesanswersviews
将n个数字插入二叉搜索树的复杂性
我有一个问题，它说"calculate the tight time complexity for the process of inserting n numbers into a binary search tree" . 它并不表示这是否是一棵 balancer 的树 . 那么，对这样的问题可以给出什么答案？如果这是一个 balancer 树，则高度为logn，插入n个数... -
271 votesanswersviews
Fibonacci序列的计算复杂性
我理解Big-O表示法，但我不知道如何为许多函数计算它 . 特别是，我一直试图弄清楚Fibonacci序列的幼稚版本的计算复杂性： int Fibonacci(int n) { if (n <= 1) return n; else return Fibonacci(n - 1) + Fibonacci(n - 2); } Fibonacci序... -
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的算法来构建后缀树，但是我不理解作者对其线性时间复杂性的解释的某些部分 . 我已经学会了算法并对其进行了编码，但是我用作信息主要信息源的文章（链接波纹管）在某些部分有点令人困惑，因此对我来说，为什么算法是线性的并不是很清楚 . 有帮助吗？... -
966 votesanswersviews
NP，NP-Complete和NP-Hard有什么区别？
NP ， NP-Complete 和 NP-Hard 之间有什么区别？ 我知道网上有很多资源 . 我想阅读你的解释，原因是它们可能与那里有什么不同，或者它在那里，我不知道 . -
0 votesanswersviews
理论计算机科学的技术定义是什么？包括哪些子字段？
理论计算机科学的技术定义是什么？ （或者，它应该是什么？） 它包含哪些主要子域，以及将它们与其他计算机科学区分开来的共性是什么？ 更具体地说：如果某些特定的研究具有直接的实践动机，目标和结果，但主要涉及非常抽象的方法，那么它是否是理论计算机科学？ 需要考虑两个例子： "Dual quaternions for rigid transformation blending"（动画的... -
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 ... -
0 votesanswersviews
稀疏矩阵乘法复杂度
我想表达两种算法的计算复杂性：稀疏矩阵稀疏向量乘法和稀疏矩阵稀疏矩阵乘法，如在Eigen或Cusparse中使用CSR表示实现的 . 我知道它取决于几个参数，尤其是每个元素中非零值的数量 . 但是，我无法找到详细说明此类算法复杂性的出版物，并使用O（）表示法表达它 . -
1 votesanswersviews
进行二进制长除时的位操作
这来自CLRS的数论章节 . 我们被要求证明二进制"paper and pencil"长除 a/b 与结果 q 和提醒 r 对位进行 O((1+lgq)lgb) 操作 . 我看到它的方式是我们为 q 中的每个位减去 b . 因此，假设减去 b 执行 lgb 操作（ b 中的每个位一个），那么我们总共有 O(lgblgq) 次操作，这不是请求的操作 . 如果考虑到您执行的第一个... -
0 votesanswersviews
深度优先搜索示例
我有一个练习考试的深度优先搜索示例，我已经问过另一个关于它的问题，我想我有一些关于它的概念...... 我只是想确认我得到的结果是否正确，如果你可以指导我做错了什么以及如何解决它 . 这是它的图片： http://i.imgur.com/FdKxIUw.png 我从DF到0的顺序得到的结果是： 1 5 7 6 2 3 4 8 9 对于父母，我感到困惑，因为它从0开始，0的父母是4？而4的父母是5？... -
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种情景，除了关于飞行员的情况之外，我们无法决定其中的任何情况 . 一家公司发明了... -
2 votesanswersviews
Boost.MPL的复杂性
boost::mpl::push_back文件说明： push_back在序列结束时执行插入，保证O（1）复杂度 . 编译时间复杂吗？ -
2 votesanswersviews
用于以 2 的幂进行集划分的多项式时间算法
与 programming/implementation 相比，这更是一个 algorithm/proof 问题，因此如果 StackOverflow 不是正确的选择，我们深表歉意。 至于问题： 假设我们有一组数字，并且每个数字都必须是一个正整数和2的幂。例如，也许我们有{1, 1, 2, 4, 8, 8, 8, 8, 128}。我们想将集合划分为A和B，其中每个元素必须恰好在A或B内，以使A的元...