相关疑难解决方法(0)

我的问题来自于"大O的简单英语解释".我不知道对数复杂性的确切含义.我知道我可以在时间和操作次数之间进行回归并计算X平方值,并确定复杂度.但是,我想知道一种在纸上快速确定它的方法.

您如何确定对数复杂度？有一些很好的基准吗？

我正在阅读有关Big O符号的内容.它说,

循环的大O是循环迭代到循环内语句数的次数.

这是一段代码片段,

for (int i=0 ;i<n; i++)
{
    cout <<"Hello World"<<endl;
    cout <<"Hello SO";
}

现在根据定义,Big O应该是O(n*2),但它是O(n).任何人都可以解释为什么会帮助我吗？谢谢,谢谢.

我试图理解数据结构和不同的算法,然后我很困惑地测量冒泡排序时间的复杂性.

for (c = 0; c < ( n - 1 ); c++) {
  for (d = 0; d < n - c - 1; d++) {
    if (array[d] > array[d+1]) /* For descending order use < */
    {
      swap       = array[d];
      array[d]   = array[d+1];
      array[d+1] = swap;
    }
  }
}

现在每个Big O都会告诉Best case O(n),Avg case(n2)和Worst Case(n2).但是当我看到代码时,发现第一阶段内部循环运行n次然后是第二阶段n - 1,n - 2等等.这意味着在每次迭代中它的值都会下降.例如,如果我有[] = {4,2,9,5,3,6,11},那么比较的总数将是 -

1st Phase - 7 time
2nd phase - 6 time
3rd Phase - 5 time
4th …

什么是复杂性:

int f4(int n)
{
   int i, j, k=1, count = 0;

   for(i = 0; i < n; i++) 
   {
      k *= 3;

      for(j = k; j; j /= 2)
         count++;
   }

   return count;
}

我知道它是O(n ^ 2)但你怎么计算这个？为什么不是n*log n？

我这里有一个简短的程序:

Given any n:
i = 0;
while (i < n) {
   k = 2;
   while (k < n) {
        sum += a[j] * b[k]
        k = k * k;
   }
   i++;
}

这个的渐近运行时间是O(n log log n).为什么会这样？我知道整个程序至少会运行n次.但我不知道如何找到日志日志n.内循环取决于k*k,所以它显然小于n.如果每次都是k/2那么它就是n log n.但是你怎么能找到答案是log log n？

可能重复:
Big O的简单英文解释

我现在已经做了4年的编程,但我从未关注过时间复杂性.我明天接受采访,我知道他们会问我关于它的问题.任何人都可以通过简单的方式帮助我理解时间复杂性吗？通过查看代码,我们如何判断它的复杂性是O(n)还是O( log n)O(n)等？

可能重复:
Big O的简单英文解释

我一直在努力计算我编写的算法的Big-O时间和空间复杂度.

任何人都可以指出一个很好的资源来研究算法的空间复杂性.

编辑:我在发布之前搜索过教程.遗憾的是,所有教程都侧重于运行时复杂性,并且几乎没有写太多关于空间复杂性的内容.

我有两个问题:

public static void method1(int[] a, int[] b) {
   int sum1 = 0, sum2 = 0;

   for(int i = 0; i < a.length; i++) {
      sum1 += a[i];
   }

   for(int i = 0; i < b.length; i++) { 
      sum2 += b[i];
   }
}

问题1:这是否在O(n)中？是否有多少循环(不是嵌套循环)method1？

问题2:如果有的话怎么办？

Arrays.sort(a);

里面method1,它有什么功能？

所以我一直试图尽可能地理解Big O符号,但仍有一些我很困惑的事情.所以我一直在读,如果有东西是O(n),它通常指的是算法的最坏情况,但它不一定要参考最坏的情况,这就是为什么我们可以说最好的例如,插入排序的大小是O(n).但是,我无法理解这意味着什么.我知道如果最坏情况是O(n ^ 2),这意味着在最坏情况下表示算法的函数增长不快于n ^ 2(存在上限).但如果你有O(n)作为最好的情况,我应该怎么读呢？在最好的情况下,算法增长不比n快？我的图片是以n为上限的图形,如

如果算法的最佳情况是O(n),那么n是算法运算在最佳情况下增长的速度的上限,因此它们不能比n增长得快......但这并不意味着它们可以像O(log n)或O(1)那样快速增长,因为它们低于上限？这没有意义,因为O(log n)或O(1)是比O(n)更好的场景,所以O(n)不是最好的情况吗？我很失落哈哈

假设我在Python 3.X中有一个列表.我使用list comprehension返回该列表的一个子集---是否有一种简单/ Pythonic的方式从原始列表中"弹出"该子集(因此返回后该子集中的元素不再在原始列表中) ？谢谢!

示例(我需要帮助定义my_func):

a = [1, 2, 2, 3, 4, 5]
a, b = my_func(a, *kwargs)

我想要:

a = [1,2,2]
b = [3,4,5]

注意:我不希望一次关闭一个值,而是一次性整个子集."流行"可能不是最好的术语,但我不知道是什么.

我能想到的最好的方法是:

 temp = [idx for idx, val in enumerate(a) if val > 2]  
 b = [a[i] for i in temp]  
 a = [val for idx,val in enumerate(a) if idx not in temp]  

显然,我更喜欢更优雅和高效的东西.我想避免两次超过列表.

编辑:我认为这个问题是独一无二的,因为我不仅仅关心拆分列表 - 我想修改原始列表.拆分并将其中一个拆分分配给原始列表变量是一种可能的解决方案,但我希望可能有一种方法可以在不明确分配给原始列表变量的情况下执行此操作(类似于b.append(a.pop(类似)) )))