我在数据结构书籍复杂性层次图中读到 n 大于 2 log n。但无法理解如何以及为什么。在使用 2 的幂作为 n 的简单示例时，我得到等于 n 的值。
书中没有提到，但我假设它以 2 为基数（因为上下文是 DS 复杂性）
a) 是
O(n) > O(pow(2,logn))？b)
O(pow(2,log n))优于O(n)？
math optimization complexity-theory time-complexity asymptotic-complexity
我正在学习这本书中的大O表示法。
\n\n大O表示法的定义是：
\n\n\n如果存在常数 C 和 k 使得 |f (x)| ，我们说 f (x) 是 O(g(x)) \xe2\x89\xa4 C|g(x)| 每当 x > k 时。\n\n\n
现在这是第一个例子：
\n\n\n示例 1 证明 f (x) = x^2 + 2x + 1 是 O(x^2)。
\n解：我们观察到，当 x > 1 时，我们可以很容易地估计 f (x) 的大小，因为 x 1。因此
\n0 \xe2\x89\xa4 x^2 + 2x + 1 \xe2\x89\xa4 x ^2 + 2x^2 + x^2 = 4x^2
\n只要 x > 1。因此，我们可以以 C = 4 和 k = 1 为证，证明 f …
函数 (1/2)^n 属于哪个 Big O 类？
从纯粹的数学角度来看，我们似乎必须将其放入 O(1) 中，因为对于任何足够大的 n，1/2^n 都接近 0。
然而，当涉及到渐近分析和大O时，我们往往会做很多手把手的工作，并且还会回顾公式。1/2 从技术上讲是一个常数，因此看起来会落入 O(c^n) 的范围。
我倾向于 O(c^n) 因为在谈论算法时说“半个操作”是没有意义的。当输入变大时，什么算法需要一半的时间？充其量，我看到数学公式 (1/2)^n 指的是某个时间常数的一半 - 比如说一分钟。所以 (30 秒)^n 变成了一个巨大的数字，并且该函数显然属于 O(c^n) 。
一点帮助？
CSC (compressed sparse column)我想知道从到 的转换的算法复杂度CSR (compressed sparse row)是多少？
说我有
m x m矩阵A = csc(m,m)nm x m矩阵B = csr(m,m)nCSC -> CSR现在我从with进行转换B = convert(A)。
它的成本和复杂程度如何？谁能指导我完成它？或者澄清事情？谢谢
我有一个问题,它说"计算将n个数字插入二叉搜索树的过程的紧迫时间复杂度".它并不表示这是否是一棵平衡的树.那么,对这样的问题可以给出什么答案？如果这是一个平衡树,则高度为logn,插入n个数字需要O(nlogn)时间.但这是不平衡的,在最坏的情况下可能需要O(n 2)时间.找到将n个数字插入bst的时间复杂度是什么意思？我错过了什么吗？谢谢
algorithm tree complexity-theory asymptotic-complexity binary-search-tree
我最近开始玩这个普林斯顿课程的算法,我观察了以下模式
上)
double max = a[0];
for (int i = 1; i < N; i++)
if (a[i] > max) max = a[i];
O(N ^ 2)
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
if (a[i] + a[j] == 0)
cnt++;
O(N ^ 3)
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
for (int k = j+1; k < …m=1;
for(i=1;i<=n;i++){
m=m*2;
for(j=1;j<=m;j++){
do something that is O(1)
}
}
上面代码的时间复杂度是多少？请告诉我如何解决这些类型的问题.
基于这个基数排序文章http://www.geeksforgeeks.org/radix-sort/我正在努力理解在排序中某些方法的时间复杂性方面正在解释什么.
从链接:
让输入整数有d位数.基数排序采用O(d*(n + b))时间,其中b是表示数字的基数,例如,对于十进制系统,b为10. d的值是多少？如果k是最大可能值,则d将是O(log_b(k)).因此总体时间复杂度为O((n + b)*logb(k)).对于大k来说,这看起来不仅仅是基于比较的排序算法的时间复杂度.让我们先来限制k.设k≤nc,其中c是常数.在这种情况下,复杂性变为O(nlogb(n)).
所以我确实理解排序需要O(d*n),因为有d个数字因此d遍,你必须处理所有n个元素,但我从那里丢失了它.一个简单的解释将非常有用.
我最近已经进入争论/辩论,我试图得到正确解决方案的明确判决.
众所周知,n!增长非常快,但究竟有多快,足以"隐藏"可能添加到其中的所有其他常量？
让我们假设我有这个愚蠢而简单的程序(没有特定的语言):
for i from 0 to n! do:
; // nothing
鉴于输入是n,那么这的复杂性显然O(n!)(或者甚至?(n!)是这里不相关).
现在让我们假设这个程序:
for i from 0 to n do:
for j from 0 to n do:
for k from 0 to n! do:
; // nothing
鲍勃声称:"这个程序的复杂性显而易见O(n)O(n)O(n!) = O(n!n^2) = O((n+2)!)."
爱丽丝回应说:"我同意你的鲍勃,但实际上这将是足够的,如果你说的复杂性O(n!),因为O(n!n^k) = O(n!)对于任何k >= 1常量".
爱丽丝是否正确地记录了鲍勃的分析？
我很确定前一个函数增长得更快.但是当我把它绘制在Wolfram alpha上时,后者似乎占主导地位.
通常,如果我想比较f(n)和g(n),可以使用log(f(n))和log(g(n))的分析来分析原始函数吗？