算法何时可以具有平方根(n)时间复杂度？

Question

有人能给我一个具有平方根(n)时间复杂度的算法的例子.平方根时间复杂度甚至意味着什么？

Answer 1

• 平方根时间复杂度意味着算法需要O(N^(1/2))评估,其中输入的大小为N.
• 作为需要O(sqrt(n))时间的算法的一个例子,Grover的算法需要花费很多时间.Grover算法是一种量子算法,用于O(sqrt(n))及时搜索n个条目的未排序数据库.

• 让我们举一个例子来理解如何O(sqrt(N))解决运行时的复杂性问题.这将是详细的,但有趣的是要理解.(以下示例,在回答此问题的上下文中,取自Coding Contest Byte:Square Root Trick,非常有趣的问题和有趣的技巧,以达到O(sqrt(n))复杂性)

  • 给定A,包含n个元素数组,实现点更新和范围求和查询的数据结构.

    • update(i,x) - > A [i]:= x(点更新查询)
    • 查询(lo,hi) - >返回A [lo] + A [lo + 1] + .. + A [hi].(范围总和查询)

  • 天真的解决方案使用数组.O(1)更新(数组索引访问)和O(hi - lo) = O(n)范围总和(从开始索引到结束索引和累加的迭代)需要时间.

  • 更有效的解决方案将阵列分成长度为k个切片并将切片和存储在数组S中.
  • 更新需要持续时间,因为我们必须更新A的值和相应S的值.在更新(6,5)中,我们必须将A [6]更改为5,这会导致将S 1的值更改为保持S最新.
  • 范围和查询很有趣.第一个和最后一个切片的元素(部分包含在查询范围中)必须逐个遍历,但对于完全包含在我们范围内的切片,我们可以直接使用S中的值并获得性能提升.
  • 在查询(2,14)中,我们得到了

 query(2, 14) = A[2] + A[3]+ (A[4] + A[5] + A[6] + A[7]) + (A[8] + A[9] + A[10] + A[11]) + A[12] + A[13] + A[14] ; 
 query(2, 14) = A[2] + A[3] + S[1] + S[2] + A[12] + A[13] + A[14] ;
 query(2, 14) = 0 + 7 + 11 + 9 + 5 + 2 + 0;
 query(2, 14) = 34;

• 更新和查询的代码是:

  def update(S, A, i, k, x):
      S[i/k] = S[i/k] - A[i] + x
      A[i] = x

  def query(S, A, lo, hi, k):
      s = 0
      i = lo
      //Section 1 (Getting sum from Array A itself, starting part)
      while (i + 1) % k != 0 and i <= hi:
          s += A[i]
          i += 1
      //Section 2 (Getting sum from Slices directly, intermediary part)
      while i + k <= hi:
          s += S[i/k]
          i += k
      //Section 3 (Getting sum from Array A itself, ending part)
      while i <= hi:
          s += A[i]
          i += 1
  return s

• 现在让我们确定复杂性.
• 每个查询都取平均值
  • 第1节平均需要k/2次.(你可以迭代至少k/2)
  • 第2节平均采用n/k时间,基本上是切片数
  • 第3节平均需要k/2次.(你可以迭代至少k/2)
  • 所以,总之,我们得到k/2 + n/k + k/2 = k + n/k时间.
• 并且,对于k = sqrt(n),这被最小化.sqrt(n)+ n/sqrt(n)= 2*sqrt(n)
• 所以我们得到O(sqrt(n))时间复杂度查询.

Answer 2

有很多例子。这些是可以在 root(n) 复杂性中解决的少数问题[也可能更好]。

• 判断一个数是否是素数。
• 格罗弗算法：允许在与输入大小的平方根成比例的时间内对未排序的输入进行搜索（在量子上下文中）。关联
• 数字的因式分解。

您将面临许多问题，需要使用sqrt(n)复杂性算法。

作为第二部分的答案：

sqrt(n) 复杂度意味着if the input size to your algorithm is n then there approximately sqrt(n) basic operations ( like **comparison** in case of sorting). Then we can say that the algorithm has sqrt(n) time complexity.

我们分析一下第三个问题就清楚了。

let's n= positive integer. Now there exists 2 positive integer x and y such that
     x*y=n;
     Now we know that whatever be the value of x and y one of them will be less than sqrt(n). As if both are greater than sqrt(n) 
  x>sqrt(n) y>sqrt(n) then x*y>sqrt(n)*sqrt(n) => n>n--->contradiction.

因此，如果我们检查 2 到 sqrt(n)，那么我们将考虑所有因素（1 和 n 是微不足道的因素）。

代码片段：

   int n;
   cin>>n;
   print 1,n;
   for(int i=2;i<=sqrt(n);i++) // or for(int i=2;i*i<=n;i++)
     if((n%i)==0)
       cout<<i<<" ";

注意：你可能会认为，不考虑重复，我们也可以通过从 1 循环到 n 来实现上述行为。是的，这是可能的，但是谁想要运行一个可以在 O(n) 中运行的程序。我们总是寻找最好的程序。

阅读 Cormen算法导论这本书。

我还会要求您阅读以下 stackoverflow 问题和答案，他们肯定会消除所有疑问:)

1. 有没有 O(1/n) 的算法？
2. 简单的英语解释 Big-O
3. 哪一个更好？
4. 如何计算大 O 复杂度？

Answer 3

质数

如其他答案中所述，与素数有关的一些基本事项需要O（sqrt（n））时间：

1. 查找除数
2. 求除数之和
3. 找到欧拉的汤to

在下面，我提到了两个高级算法，它们在复杂性上也都带有sqrt（n）项。

MO的算法

试试这个问题：强大的数组

我的解决方案：

#include <bits/stdc++.h>
using namespace std;
const int N = 1E6 + 10, k = 500;

struct node {
    int l, r, id;
    bool operator<(const node &a) {
        if(l / k == a.l / k) return r < a.r;
        else return l < a.l;
    }
} q[N];

long long a[N], cnt[N], ans[N], cur_count;
void add(int pos) {
    cur_count += a[pos] * cnt[a[pos]];
    ++cnt[a[pos]];
    cur_count += a[pos] * cnt[a[pos]];
}
void rm(int pos) {
    cur_count -= a[pos] * cnt[a[pos]];
    --cnt[a[pos]];
    cur_count -= a[pos] * cnt[a[pos]];
}

int main() {
    int n, t;
    cin >> n >> t;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < t; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q, q + t);
    memset(cnt, 0, sizeof(cnt));
    memset(ans, 0, sizeof(ans));

    int curl(0), curr(0), l, r;
    for(int i = 0; i < t; i++) {
        l = q[i].l;
        r = q[i].r;

/* This part takes O(n * sqrt(n)) time */
        while(curl < l)
            rm(curl++);
        while(curl > l)
            add(--curl);
        while(curr > r)
            rm(curr--);
        while(curr < r)
            add(++curr);

        ans[q[i].id] = cur_count;
    }
    for(int i = 0; i < t; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

查询缓冲

尝试此问题：一棵树上的查询

我的解决方案：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, k = 333;

vector<int> t[N], ht;
int tm_, h[N], st[N], nd[N];
inline int hei(int v, int p) {
    for(int ch: t[v]) {
        if(ch != p) {
            h[ch] = h[v] + 1;
            hei(ch, v);
        }
    }
}
inline void tour(int v, int p) {
    st[v] = tm_++;
    ht.push_back(h[v]);
    for(int ch: t[v]) {
        if(ch != p) {
            tour(ch, v);
        }
    }
    ht.push_back(h[v]);
    nd[v] = tm_++;
}

int n, tc[N];
vector<int> loc[N];
long long balance[N];
vector<pair<long long,long long>> buf;
inline long long cbal(int v, int p) {
    long long ans = balance[h[v]];
    for(int ch: t[v]) {
        if(ch != p) {
            ans += cbal(ch, v);
        }
    }
    tc[v] += ans;
    return ans;
}
inline void bal() {
    memset(balance, 0, sizeof(balance));
    for(auto arg: buf) {
        balance[arg.first] += arg.second;
    }
    buf.clear();
    cbal(1,1);
}

int main() {
    int q;
    cin >> n >> q;
    for(int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        t[x].push_back(y); t[y].push_back(x);
    }
    hei(1,1);
    tour(1,1);
    for(int i = 0; i < ht.size(); i++) {
        loc[ht[i]].push_back(i);
    }
    vector<int>::iterator lo, hi;
    int x, y, type;
    for(int i = 0; i < q; i++) {
        cin >> type;
        if(type == 1) {
            cin >> x >> y;
            buf.push_back(make_pair(x,y));
        }
        else if(type == 2) {
            cin >> x;
            long long ans(0);
            for(auto arg: buf) {
                hi = upper_bound(loc[arg.first].begin(), loc[arg.first].end(), nd[x]);
                lo = lower_bound(loc[arg.first].begin(), loc[arg.first].end(), st[x]);
                ans += arg.second * (hi - lo);
            }
            cout << tc[x] + ans/2 << '\n';
        }
        else assert(0);

        if(i % k == 0) bal();
    }
}