相关疑难解决方法(0)

我正在学习算法分析.我无法理解O,Ω和Θ之间的差异.

它们的定义方式如下:

• f(n) = O(g(n))装置c · g(n)是一个上限f(n).因此存在一些常数c,使得f(n)总是≤ c · g(n),对于足够大的n (即,n ? n0对于某一常数n0).
• f(n) = ?(g(n))装置c · g(n)是一个下界f(n).因此存在一些常数c,f(n)总是≥ c · g(n),对于所有人n ? n0.
• f(n) = ?(g(n))意味着c1 · g(n)是对上限f(n)和c2 · g(n)一个下限f(n),对于所有n ? n0.因此存在常数c1和c2 使得f(n) ? c1 ·g(n)和f(n) …

我试图理解"Eratosthenes的筛子".这是我的算法(下面的代码),以及我无法理解的功能列表(按顺序).

1. 为什么i * i效率更高i * 2？是的,我可以理解它会减少迭代次数,因此效率更高,但是它不会跳过一些数字(例如i = 9 => j = 81 skips 18 27 36 ...)？
2. 在维基百科上,我发现空间复杂度等于O(n)并且这是可以理解的; 无论我们输入什么数字,它都会创建一个输入大小的数组,但这里的时间复杂性让事情变得混乱.我发现了这种符号O(n(logn)(loglogn))- 那是什么？根据我的理解,我们有2次完整迭代和1次部分迭代O(n^2 * logn).

#include <iostream>
using namespace std;

int main() {
  cout << "Enter number:" << endl;

  int arrSize;
  cin >> arrSize;

  bool primesArr[arrSize];
  primesArr[0] = false;
  for (int i = 1; i < arrSize; i++) primesArr[i] = true;

  for (int i = 2; i < arrSize; i++)

    if …

我现在有这个方法工作正常:

 private static List<long> GetPrimeNumbers(long number)
        {
            var result = new List<long>();
            for (var i = 0; i <= number; i++)
            {
                var isPrime = true;
                for (var j = 2; j < i; j++) 
                {
                    if (i % j == 0) 
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    result.Add(i);
                }
            }
            return result;
        }

以上是最好的算法吗？

当数字超过100000时,它真的很慢.

我的意思是,找到小于或等于给定数字的素数的最佳,最高效的算法是什么？