相关疑难解决方法(0)

这是一个普遍的问题,它可以适用于任何给定的语言,如C,C++,Java等.
我认为你实现它的任何方式,你不能比使用2个循环更有效,这提供了n ^ 2的效率.

for(i=0;i<n;i++)
 for(j=0;j<n;j++)
  a[i][j]=1;

我最近在接受采访时被问到这个问题,并且想不出更有效的方法.我从访调员那里得到的是,我可以使用递归或将2D数组转换为链表,使其比n ^ 2更有效.任何人都知道这是否可能,如果有,怎么样？至少在理论上,如果不是实际的话.

编辑:实际的问题给了我两个单元格的坐标,我必须用1填充所有可能的最短路径所采用的路径.例如,如果我有一个5x5矩阵,我的两个坐标是(2,0)和( 3,3),我必须填写:
(2,0)(2,1)(2,2)(2,3)(3,0)(3,1)(3,2)(3, 3)
同时留下其余的细胞.

我一直在做Big-O的自学.我理解如何给算法提供以下符号的示例:

上):

for(int i = 0; i < n; i++)
    sum++;

O(N ^ 2):

for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

O(N ^ 3):

for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

我遇到过这些我不太了解的符号.如何根据算法提供这些示例？

也许我应该这样说:写一个算法,运行时间与以下成比例:

1. O((N ^ 3)/ 4)
2. log n ^ 3
3. O((日志^ 2)N)+ O(n)的
4. 4 ^ N
5. N R个3/2

如果我有这样的功能:

void myfunction(node* root)
{
   for(int i = 0; i<root->children.size();i++)
   {
      myfunction(root->children[i]);
   }
}

那是n ^ 2的大O还是n的大O？如果你有一个for循环并且在for循环中有一个函数调用它自己,那么Big O迭代次数是函数的吗？

我试图找到一个很好的解释来快速理解Big O和Theta理论.我总觉得可以用百万种不同的方式给出解释,我想我正在寻找最终有意义的解释.我知道这是一个n00b问题,但任何帮助将不胜感激......