Время выполнения для сита Эратосфена - PullRequest
Новая
       27

Время выполнения для сита Эратосфена

0 голосов
/ 14 декабря 2018

В настоящее время я работаю над изготовлением сита для школы.Вот мой код на данный момент: 

public static List<Integer> sieve(int input) {
    int[] numbers = new int[input - 2 + 1];
    int prime = 2; 
    // start of with 2 since first prime w/ specific multiples
    int counter = 0;
    for (int i = prime; i <= input; i++) {
      numbers[counter] = i;
      counter++;
    }

    // Main sieve logic: remove all multiples of that number (except itself), move onto next number in ArrayList (which must be prime)

  for (int x = 0; x < numbers.length; x++) {
    for (int j = findIndex(numbers, prime) + 1; j < numbers.length; j++) {
      if (numbers[j] % prime == 0) {
        numbers[j] = 0;
      } 
    }


    for (int k = findIndex(numbers, prime) + 1; k < numbers.length; k++) {
      if (numbers[k] != 0) {
        prime = numbers[k];
        break;
      }
    }

  }



    pushZerosToEnd(numbers, numbers.length);

    List<Integer> cleanerResult = new ArrayList<>();

    for (int y = 0; y < numbers.length; y++) {
      if (numbers[y] != 0) {
        cleanerResult.add(numbers[y]);
      }
    }

    return cleanerResult;
  }

// Assume that pushZerosToEnd() and findIndex() do their specified action

Поскольку это включает в себя много циклов, я знаю, что этот метод не будет эффективным или будет иметь большое время выполнения для больших входов.Однако, как мне найти среднее время выполнения (в Big O) моего текущего кода?

...