-
270 votesanswersviews
Big-O和Little-O表示法之间的区别
Big-O 符号 O(n) 和 Little-O 符号 o(n) 之间有什么区别? -
1 votesanswersviews
最坏的情况下时间复杂
未排序的n个数字列表,在具有最小差异的列表中找到任意两个数字 . 如果我必须为此编写算法,最坏的情况时间 O(nlogn) . 以下算法可以工作: 使用合并排序的排序列表 遍历整个列表一次,找出连续数字之间的差异 . 返回最小差异的数字 . 这种算法的时间复杂度是: O(nlogn + n) 我可以说 O(nlogn) ? -
0 votesanswersviews
排序算法复杂性的证明[重复]
这个问题在这里已有答案: Is log(n!) = Θ(n·log(n))? 9个答案 该定理表示: 任何比较排序算法在最坏的情况下执行Ω(nlg(n))比较 . 证明我发现: 查看算法执行的最差情况下的比较次数,意味着在其决策树中从根到叶的最长路径 . 作为高度为h的二叉树,最多有2 ^ h叶子,并且有n!排列(输出),我们有: 2 ^h≥n! 我知道我们可以将 2^h ≥ n! 重写为... -
1 votesanswersviews
有效地重新 balancer 2 ^ n-1个节点的树?
我偶然发现了这个问题:给定一个具有2 ^ n-1个节点的二叉搜索树,给出一个有效的算法将其转换为自 balancer 树(如avl或RB树) . 并分析其最坏情况下的运行时间作为n的函数 . 我认为最有效的算法是在n(n)时间为n个节点,但2 ^ n-1节点是棘手的部分 . 知道什么是运行时间呢? 任何帮助将不胜感激 -
4 votesanswersviews
将n个数字插入二叉搜索树的复杂性
我有一个问题,它说"calculate the tight time complexity for the process of inserting n numbers into a binary search tree" . 它并不表示这是否是一棵 balancer 的树 . 那么,对这样的问题可以给出什么答案?如果这是一个 balancer 树,则高度为logn,插入n个数... -
2 votesanswersviews
两个二叉搜索树的幼稚合并的时间复杂性
我看到了一个非常短的算法来合并两个二叉搜索树 . 我很惊讶它是多么简单而且非常低效 . 但当我试图猜测它的时间复杂性时,我失败了 . 让我们有两个不可变的二进制搜索树(不 balancer ),它包含整数,你想用伪代码中的下面的递归算法将它们合并在一起 . 函数 insert 是辅助的: function insert(Tree t, int elem) returns Tree: if ... -
34 votesanswersviews
如何在排序的链表上应用二进制搜索O(log n)?
最近我在链表上遇到了一个有趣的问题 . 给出了单独排序的列表,我们必须从该列表中搜索一个元素 . 时间复杂度不应超过 O(log n) . 这似乎我们需要在此链表上应用二进制搜索 . 怎么样?由于链表不提供随机访问,如果我们尝试应用二进制搜索算法,它将达到O(n),因为我们需要找到列表的长度并转到中间 . 有任何想法吗? -
0 votesanswersviews
您如何估计此算法的时间复杂度?
令N =顶点数M =有向图G的边数 . 我们以邻接列表的形式存储边 . 为清楚起见,我们假设,Oi是顶点i的outdegree,Ii是顶点i的in-degree . 算法如下: for each vertex i for each vertex j in i's adj.list //do some work for each vertex k in j's adj.list ... -
0 votesanswersviews
将顺序搜索与二进制搜索进行比较
假设我有一个未排序的实数数组,长度为 N . 我想找到最大的非正数 y ,然后在数组中找到小于 y 的第一个数字 x ,并且第一个数字 z 大于 y . 我想理论上将顺序搜索与二进制搜索非渐近地比较(即不仅仅是用大的Os)来找到这些值 . 陈述是否合理: 顺序搜索需要 0 排序比较, 3*N 搜索比较(三次连续搜索) . 二进制搜索需要 2*N*ln(N) ≈ 1.39*N... -
0 votesanswersviews
杂耍算法
方法(一种杂耍算法)将数组分成不同的集合,其中集合的数量等于n和d的GCD,并在集合中移动元素 . 如果GCD对于上面的示例数组(n = 7和d = 2)是1,那么元素将仅在一个集合内移动,我们只是从temp = arr [0]开始并继续移动arr [I d]到arr [I]并最终将temp存储在正确的位置 . 这是n = 12和d = 3的例子.GCD是3和 设arr []为{1,2,3,4,5... -
0 votesanswersviews
线性时间单对最短路径算法?
是否有一种算法可以解决 linear time 中的单对最短路问题(即有向和无向边或无向边表示为两个有向边), negative, real edge-weights 和 non-negative cycles ? Wikipedia仅提及问题的单源和全对变体的算法 . 我知道解决其中一个问题的这些问题也解决了单对问题,但是它们都没有在线性时间和所有上述标准中起作用 . 因此,对于具有上述所有标准...