-
156 votesanswersviews
是否有比Bogosort（a.k.a Monkey Sort）更差的排序算法？ [关闭]
我的同事们带我回到了我的大学时代，今天早上讨论了排序算法 . 我们回忆起我们的最爱，如StupidSort，我们其中一个人确信我们已经看到了一个 O(n!) 的排序算法 . 这让我开始寻找我能找到的"worst"排序算法 . 我们假设一个完全随机的排序会非常糟糕（即随机化元素 - 它是否按顺序排列？没有？再次随机化），我环顾四周，发现它显然被称为BogoSort, or Mon... -
1 votesanswersviews
设计O（1）数据结构
如何在常量时间内实现支持以下内容的数据结构 . 我在面试时得到了这个问题，以下是我的解决方案 . 如果您有方法，请检查我的方法，或建议更好的替代方法 . //////////////////////////////////////////////////////////////// // Implement a container that have the following methods: ... -
270 votesanswersviews
Big-O和Little-O表示法之间的区别
Big-O 符号 O(n) 和 Little-O 符号 o(n) 之间有什么区别？ -
150 votesanswersviews
大Ө符号究竟代表什么？
我真的很困惑大O，大欧米茄和大Theta符号之间的差异 . 我知道大O是上界，大欧米茄是下界，但大Ө（theta）究竟代表什么？ 我读过它意味着 tight bound ，但这是什么意思？ -
4 votesanswersviews
确定性无上下文语法与无上下文语法？
我正在读我的比较语言课的笔记，我有点困惑...... 无上下文语法和确定性无上下文语法之间有什么区别？我特别在阅读解析器如何用于CFG的解析器是O（n ^ 3），而编译器对于DCFG来说是O（n），并且并不真正理解时间复杂度的差异如何如此之大（更不用说我是仍然混淆了使CFG成为DCFG的特征 . 非常感谢你提前！ -
3 votesanswersviews
空间复杂性示例
所以我想知道在for循环中何时创建对象（或基元），这对空间复杂性有何影响？ 例如，下面是一个代码示例： public boolean checkUnique(String p){ int term = -1; int len = p.length(); for (int i =0; i<len; i++) { char c = p.charAt(i);... -
0 votesanswersviews
TextRank算法空间和时间复杂度
我试图确定TextRank的空间和时间复杂度本文中列出的算法：https://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf 由于它使用的PageRank的复杂度为：O（nm）（n - 节点数，m - 弧/边数），我们在迭代中运行它/直到收敛关键字提取的复杂性我认为它将是：O （i *（nm））并且使用邻接矩阵将空间复杂度设为O... -
3 votesanswersviews
迭代加深如何影响时间复杂度？
我有一个树遍历算法，它通常在O（bm）中运行，其中b是分支因子，m是最大深度 . 使用迭代加深，该算法一次又一次地运行，在增加的深度m次： O（bm）=b⁰b¹b²... bm 基于我对时间复杂度的有限理解，我们采用最大元素，因为随着时间的推移，这是最重要的元素，因此元素将是bm，其中m是达到的最大深度 . 因此，根据这些知识，我会得出结论，迭代加深算法也在O（bm）中运行 . 但是，从逻辑的角度... -
0 votesanswersviews
二叉搜索树的时间效率
为了插入二叉搜索树的时间效率， 我知道插入的最佳/平均情况是O（log n），其中最坏的情况是O（N） . 我想知道的是，除了实施AVL（ balancer BST）之外，是否有任何方法可以确保我们在插入时始终具有最佳/平均情况？ 谢谢！ -
173 votesanswersviews
O（nlogn）算法 - 在二进制字符串中找到三个均匀间隔的算法
我昨天在算法测试中遇到了这个问题，我无法弄清楚答案 . 它让我绝对疯狂，因为它值得大约40分 . 我认为大多数课程没有正确解决，因为我在过去24小时内没有提出解决方案 . 给定长度为n的任意二进制字符串，如果存在则在字符串中找到三个均匀间隔的字符串 . 编写一个算法，在O（n * log（n））时间内解决这个问题 . 所以像这样的字符串有三个“均匀间隔”的字符串：11100000,01001001... -
6 votesanswersviews
O（logn）总是一棵树吗？
我们总是看到（二元搜索）树上的操作具有O（logn）最差情况下的运行时间，因为树高是logn . 我想知道我们是否被告知算法的运行时间是logn的函数，例如mnlogn，我们可以得出结论它必须涉及（增强的）树吗？ 编辑：感谢您的评论，我现在意识到分治和二叉树在视觉/概念上是如此相似 . 我从来没有在两者之间 Build 联系 . 但我想到一个案例，其中O（logn）不是一个分治算法，它涉及一棵没有... -
1 votesanswersviews
部分选择排序vs Mergesort找到“k最大的数组”
我想知道我的思路是否正确 . 我正在准备面试（作为一名大学生），我遇到的一个问题是在阵列中找到K个最大的数字 . 我的第一个想法是仅使用部分选择排序（例如，从第一个元素扫描数组并保留两个变量用于所见的最低元素及其索引，并在数组末尾与该索引交换并继续这样做直到我们'我交换了K个元素并返回该数组中前K个元素的副本） . 但是，这需要 O(K*n) 时间 . 如果我只是使用像Mergesort这样的高效... -
2 votesanswersviews
了解合并排序和快速排序的运行时间
对于合并排序和快速排序，我试图想出最糟糕的情况 . 如果我是正确的，在排序所有内容时合并排序最差的情况O（nlogn） . 快速排序最糟糕的情况是当枢轴处于最不理想的位置，并且数组被排序，因此它变为O（n ^ 2） . 我想知道这是否正确，所以如果没有，请纠正我 . 我真正的问题是，如果快速排序的数据库位于数组的中间，那么数组必须是什么才能使它成为O（n ^ 2）？ -
1 votesanswersviews
是否存在不是 balancer 二叉搜索树的 balancer 二叉树？什么是时间复杂度？
是否存在不是 balancer 二叉搜索树的 balancer 二叉树？如果是这样，那么在这样的树中搜索节点的时间复杂度是多少 . 我的理解是这样的： 二叉树：任何节点都有两个最大叶节点 . 在二叉树中搜索，使用DFS或BFS是O | V E | 二进制搜索树：BST是有序节点的树 . 在二叉搜索树中搜索，使用DFS是O | log n | balancer 树（假设高度 balanc... -
2 votesanswersviews
算法的最坏情况怎么会有不同的界限？
我一直试图弄清楚这一点 . 其他一些线程解决了这个问题，但我真的不明白答案 . 还有许多答案相互矛盾 . 我知道算法永远不会超过上限，永远不会比下限更快 . 但是，我不知道最佳案例时间存在上限，最坏情况时间存在下限 . This question really threw me in a loop.我无法绕过这个...给定的运行时间可以有不同的上限和下限？ 例如，如果有人问：“显示大小为n的堆上... -
6 votesanswersviews
二元搜索的复杂性
我正在观看Berkley Uni的在线讲座并坚持下面的内容 . Problem ：假设您有一个已经排序的CD集合 . 您要查找 Headers 以"Best Of."开头的CD列表 Solution ：我们将使用二分搜索来查找"Best Of"的第一个案例，然后我们打印直到瓷砖不再"Best Of" Additional question... -
0 votesanswersviews
二进制搜索的算法时间复杂度
我想弄清楚算法的时间复杂度是什么，我有二进制搜索算法，一般是O（log n），我知道 . 但我搜索两个常数，即x = 1和x = 2 ^ 31 - 1（整数的大小） . 我认为在最坏的情况下，我的时间复杂度是log2（2 ^ 31）= 31，所以在最坏的情况下二进制搜索需要31步 . 然而，二进制搜索中的每一步我都调用一个函数，它具有O（n）运行时（只有一个输入大小的循环） . 我的算法是否只... -
-3 votesanswersviews
二进制搜索字符串的复杂性
我有一个排序的字符串数组：例如：[“bar”，“foo”，“top”，“zebra”]我想搜索输入字是否存在于数组中 . 例如： search (String[] str, String word) { // binary search implemented + string comaparison. } 现在二进制搜索将考虑复杂度，即O（logn），其中n是数组的长度 . 所以这么... -
0 votesanswersviews
对于faser搜索，在进行二分查找之前不应该对数据进行合并排序，或者直接跳转到线性搜索？
我正在学习算法并且在某些情况下对它们的应用有疑问 . 存在分而治之的合并排序和二元搜索 . 两者都比线性增长更快 . 假设我想在大量数据列表中搜索某些值 . 我不知道数据是否已排序 . 如何不进行线性搜索，为什么不首先进行合并排序然后进行二元搜索 . 会更快吗？或者应用合并排序然后结合二进制搜索的过程会比线性搜索更慢吗？为什么？它取决于数据的大小吗？ -
2 votesanswersviews
balancer 二叉树与 balancer 二进制搜索树
对于这些操作中的每一个， balancer 二叉搜索树是否会比 balancer 二叉树更快地完成任务？ 查找树中的最小项目 . 我认为 balancer 的BST比 balancer 的二进制树有更快的时间，因为你可以保持向左移动并找到最小的项目 . 我认为这将是O（log n） . 创建树中所有小于某个值v的元素的列表 . 对于2，有人可以给我一个关于哪一个会有更快的大时间的解释吗？ -
1 votesanswersviews
二进制搜索运行时中的某些异常
我有一个二进制搜索的修改版本，它以排序顺序和一个值接收一个数组，并返回一个等于或大于给定值的元素的最小可能索引（如果该值大于该值，则返回-1）最大） 运行上述算法后，一切正常，方法按预期工作 . 但是，我在不同的输入大小上运行它来测量运行时 . for(int i=1;i<=20;i++){ int size=10*(i*i*i*i); int[] array=createRand... -
0 votesanswersviews
为什么二进制搜索算法中的赋值不会增加时间复杂度？
对于插入排序更糟糕的情况，其中存在n个递减元素的数组 . comparing 所有元素从左到右花费的总时间是： 1 2 ...（n - 2）（n - 1） 在计算时间复杂度时也考虑了这些元素，这也是： 1 2 ...（n - 2）（n - 1） 最终，我们到达O（n ^ 2） . 采取另一种算法，如二元搜索; the act of finding a midpoint ，然后... -
1 votesanswersviews
有效地重新 balancer 2 ^ n-1个节点的树？
我偶然发现了这个问题：给定一个具有2 ^ n-1个节点的二叉搜索树，给出一个有效的算法将其转换为自 balancer 树（如avl或RB树） . 并分析其最坏情况下的运行时间作为n的函数 . 我认为最有效的算法是在n（n）时间为n个节点，但2 ^ n-1节点是棘手的部分 . 知道什么是运行时间呢？ 任何帮助将不胜感激 -
3 votesanswersviews
Apache Spark RDD sortByKey算法和时间复杂度
Apache Spark RDD sortByKey的Big-O时间复杂度是多少？ 我正在尝试根据特定订单将行号分配给RDD . 假设我有一个{K，V}对RDD，我希望按键执行订单 myRDD.sortByKey(true).zipWithIndex 这个操作的时间复杂度是多少？ 而且幕后发生了什么？泡泡排序？我希望不是！我的数据集非常大并且跨分区运行，所以我很好奇sortByKey函数是否是最... -
95 votesanswersviews
哈希表真的可以是O（1）吗？
哈希表可以实现O（1）似乎是常识，但这对我来说从来没有意义 . 有人可以解释一下吗？以下是两种情况： A. The value is an int smaller than the size of the hash table. 因此，该值是它自己的哈希值，因此没有哈希表 . 但如果有，那将是O（1）并且仍然是低效的 . B. You have to calculate a hash of t... -
0 votesanswersviews
找到一个有效的算法来获得一条线
给定n个水平线段，其中每个线段的范围是x2 - x1，我应该应用什么算法来获得一条直线，它让我获得最大的 combined 范围（每个线段与一个线段相加会增加该线段的范围），就像发现一样钻一条线，以获得最大量的水（水代表具有X2-X1数量的区段）我完成了蛮力算法，令人沮丧 big O (n^4) -
-1 votesanswersviews
Python内置函数时间/空间复杂性
对于python内置函数，例如： sorted() min() max() 什么是时间/空间复杂性，使用什么算法？ 是否总是建议使用python的内置函数？ -
3 votesanswersviews
R和大数据分析[关闭]
我正在寻找关于使用R来分析大数据的一些建议 - 即，遇到TB的数据 . 通常我认为最好预处理数据并仅加载用户执行分析所需的信息 . 但是，如果需要聚合来自大型数据集（例如，200 GB）的信息，我认为首先，将数据存储在列数据库而不是面向行的DBMS中会更有效 . 其次，对于CPU密集型数据分析，使用RHadoop / RHIPE获得一些分布式计算功能可能是值得的 . 此外，如果有多个企业用户，那么... -
4635 votesanswersviews
什么是“大O”符号的简单英语解释？
我更喜欢尽可能少的正式定义和简单的数学 . -
32 votesanswersviews
这个算法是线性的吗？
受到这两个问题的启发：String manipulation: calculate the "similarity of a string with its suffixes"和Program execution varies as the I/P size increases beyond 5 in C，我提出了以下算法 . 问题将是 这是正确的，还是我在推理中犯了错误？...