相关疑难解决方法(0)

如果我有这样的功能:

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迭代次数是函数的吗？

我正在尝试解决 BinarySearch.com 上的一个问题：

给定一个按升序排序的整数 nums 和一个整数 k 的列表，返回列表中的任意两个元素加起来是否为 k。您不能两次使用相同的元素。注意：数字可以是负数或 0。这应该在O(1)空格中完成。
所以对于nums = [1, 3, 5, 8]和k = 6，答案应该是true。

我知道它可以使用两个指针来完成，但我正在学习二进制搜索，所以我想出了以下逻辑：

bool solve(vector<int>& nums, int k) {
    for(int i=0; i<nums.size(); i++) {
        auto loc=lower_bound(begin(nums), end(nums), k-nums[i]);
        if(loc!=nums.end()) {
            if(distance(nums.begin(), loc)!=i && *loc+nums[i]==k) return true;
        }
    }
    return false;
}

它被接受了，但时间复杂度是多少？我不确定是O(NlogN)因为我O(logN)对 中的每个值运行二分搜索（算法）nums，还是应该是O(N^2)因为当if条件为真时，我使用distance()，据我所知，这O(n)本身就是一个操作。

我很难理解算法的效率,你如何确定,特定的句子或部分是lg n,O(N)还是log base 2(n)？

我在这里有两个例子.

doIt()可以表示为O(n)= n ^ 2.

第一个例子.

i=1
loop (i<n)
doIt(…)
i=i × 2 
end loop  

以上费用如下:

i=1                                ... 1
loop (i<n)                         ... lg n
doIt(…)                            ... n^2 lg n
i=i × 2                            ... lg n
end loop 

第二个例子:

static int myMethod(int n){
    int i = 1;
    for(int i = 1; i <= n; i = i * 2)
          doIt();
    return 1;
}

以上费用如下:

static int myMethod(int n){                      ... 1
    int i = 1;                                   ... 1
    for(int …

假设我有一个if子句

if (!f(x))
{
   g(x);
}

f(x)= O(x ^ 3)的复杂度和g(x)= O(x ^ 2)的复杂度.在这种情况下,整体复杂性是多少？O(x ^ 5)？还是O(x ^ 3)？

我想增加问题的大小.

while(z(x))
{
  for(p(x))
  {
     if (!f(x))
     {
       g(x);
     }
  }
}

其中,z(x)= O(x ^ 5),p(x)= O(x),f(x)= O(x ^ 3),g(x)= O(x ^ 2)

我是时间复杂度分析的新手...

如果有人能告诉我这是否是二次的，我将不胜感激。而且如果有更简单的方法可以使它成为o(1)。

public class PrimeNumbers {
    public boolean isPrime(int n) {
        boolean retValue = true;
        for (int i = 2; i < n; i++) {
            if (n % 2 == 0) {
                retValue = false;
            }
        }
        return retValue;
    }
}

如果有人可以分解它为什么是这样，它肯定会帮助我学习。:)

非常感谢！

在下面的循环中是复杂度O（1）还是O（n）？

for(int j = 0; j < Math.random() * 1000 + 1; j++)

我不知道它在循环中运行的次数，所以不应该是O（n）吗？