我需要计算以下代码的时间复杂度:
for (i = 1; i <= n; i++)
{
for(j = 1; j <= i; j++)
{
// Some code
}
}
是O(n ^ 2)？
我正在为期末考试而学习,档案中有一个问题我无法找到答案:
一种算法运行时间的增长顺序为O(N ^ 2); 第二算法的运行时间的增长顺序为O(N ^ 3).列出程序员更喜欢使用O(N ^ 3)算法而不是O(N ^ 2)算法的三个引人注目(逻辑,令人信服)的原因.
如何计算递归算法的时间复杂度？
int pow1(int x,int n) {
if(n==0){
return 1;
}
else{
return x * pow1(x, n-1);
}
}
int pow2(int x,int n) {
if(n==0){
return 1;
}
else if(n&1){
int p = pow2(x, (n-1)/2)
return x * p * p;
}
else {
int p = pow2(x, n/2)
return p * p;
}
}
我正在研究测试并发现了这个问题:
我无法确定复杂性,我认为它是O(n 2)或O(n 3)而我倾向于O(n 3).
有人能告诉我它是什么以及为什么？
我认为它是O(n 2)是因为在j循环中,j = i它给出了一个三角形的形状,然后k循环从i + 1到j,我认为是三角形的另一半.
public static int what(int[] arr)
{
int m = arr[0];
for (int i=0; i<arr.length; i++)
{
for (int j=i; j<arr.length;j++)
{
int s = arr[i];
for (int k=i+1; k<=j; k++)
s += arr[k];
if (s > m)
m = s;
}
}
return m;
}
如果你能告诉我它的作用吗？
我想它返回正整数的加法或数组中的最大整数.
但对于像{99, -3, 0, 1}它这样的数组返回99 …
remove()Java中Priority Queue类的函数的复杂性(大哦)是多少？我无法在任何地方找到任何记录,我认为它是O(n),考虑到你必须在删除之前找到该元素然后重新洗牌.但我看到其他人不同意并认为这是O(登录).有任何想法吗？
我知道快速排序和合并排序都需要O(n)辅助空间用于构造的临时子数组,并且就地快速排序需要O(log n)辅助空间用于递归堆栈帧.但是对于堆排序,似乎它也有最坏的O(n)辅助空间来构建临时堆,即使节点只是指向实际元素的指针.
我遇到了这个解释:
只需要额外的O(1)空间,因为堆是在要排序的数组中构建的.
但我认为这意味着原始数组必然已经被实现为某种树？如果原始数组只是一个向量,那么似乎仍然需要分配堆的内存.
我知道mergesort的最坏情况是O(nlogn),与普通情况相同.
但是,如果数据是升序或降序,则会导致最小比较次数,因此mergesort变得比随机数据快.所以我的问题是:什么样的输入数据产生最大数量的比较,导致mergesort变慢？
这个问题的答案是:
对于某些排序算法(例如快速排序),元素的初始顺序可能会影响要完成的操作数.然而,它不会对mergesort进行任何更改,因为它必须完全执行相同数量的操作:递归地划分为小数组,然后将它们合并回来,总Θ(nlogn)时间.
但这是错误的.在这一点上,我们有两个子阵列,如果初始数据已经排序,我们想要合并它们,我们将只进行n/2次比较.这是第一个子阵列的所有元素,只有第二个数组的第一个元素.但是,我们可以实现更多目标.我正在寻找输入数据.
通常,一些答案提到给定的解决方案是线性的,或者另一个解决方案是二次的.
如何区分/识别什么是什么？
对于像我这样仍然不知道的人,有人可以解释这个,这是最简单的方法吗？
我想知道python 2.7中对象most_common提供的函数的复杂性是多少collections.Counter.
更具体地说,是Counter保持某种排序列表,当它被更新,允许执行的most_common速度比运行O(n)时n添加计数器的(唯一的)项目的数量？为了您的信息,我正在处理一些大量的文本数据,试图找到第n个最常见的令牌.
我检查了官方文档(https://docs.python.org/2/library/collections.html#collections.Counter),CPython wiki(https://wiki.python.org/moin/TimeComplexity)但我可以找不到答案.先感谢您!
罗曼.