Блог

Главная - Вопросы по программированию - Какова временная сложность этого решения?

Какова временная сложность этого решения?

#c #arrays #time-complexity #big-o

Вопрос:

Я пытаюсь лучше понять временную и пространственную сложность различных решений. Эта программа находит левую и правую сумму массива. Я почти уверен, что это O(n) O(n). Кто-нибудь может подтвердить?

 vector<int> arrayOfProducts(vector<int> array) {
    vector<int> vec;
    for (int i = 0; i < array.size(); i  ) {

      int leftidx = i - 1, rightidx = i   1;
      int leftSum = 1, rightSum = 1, totalSum = 1;

      if (leftidx >= 0){
         while (leftidx >= 0){
           leftSum *= array[leftidx];
           leftidx--;
          }
       }

     if (rightidx < array.size()) {
         while (rightidx < array.size()) {
             rightSum *= array[rightidx];
             rightidx  ;
         }
     }
    totalSum = leftSum * rightSum;
    vec.push_back(totalSum);

  }
return vec;

}

Комментарии:

1. Можете ли вы дать более подробную информацию о том, почему вы почти уверены, что это O(n) O(n)? На первый взгляд я вижу вложенные циклы, я думаю, O(n^2). Не имеет отношения к сложности времени, но вы вычисляете сумму, многократно вызывая *= ?

2. Я почти уверен, что это можно сделать в O(N), но Натан прав, что этот код этого не делает.

3. Если быть точным, то каждый вывод, по-видимому, является произведением всех элементов массива, кроме того, который находится в позиции i . Это можно было бы вычислить, сначала найдя произведение всех элементов массива в O(N), а затем разделив его на каждый отдельный элемент.

4. Если размер вектора равен N , то сначала while выполняется 0 1 2 … N-1 раз, а второй N-1 N-2 … 0 раз. Поскольку оба они равны O(N^2), сложность составляет O(2*N^2), что равно O(N^2)

Ответ №1:

Вам может быть интересно, что Google Benchmark может оценить сложность алгоритмов для вас.

Вы можете скачать библиотеку тестов здесь и пример теста сложности здесь. Создание библиотеки должно быть простым, если вы прочтете инструкции здесь. Вам понадобится git cmake. Если вы не хотите его устанавливать, вы можете воспользоваться онлайн-сервисом здесь

Например, я попробовал это

 std::vector<int> arrayOfProducts(const std::vector<int>amp; array) 
{
  std::vector<int> vec;
  for (int i = 0; i < array.size(); i  ) 
  {
    int leftidx = i - 1, rightidx = i   1;
    int leftSum = 1, rightSum = 1, totalSum = 1;

    if (leftidx >= 0){
        while (leftidx >= 0){
          leftSum *= array[leftidx];
          leftidx--;
        }
      }

    if (rightidx < array.size()) {
        while (rightidx < array.size()) {
            rightSum *= array[rightidx];
            rightidx  ;
        }
    }
    totalSum = leftSum * rightSum;
    vec.push_back(totalSum);
  }
  return vec;
}

static void TimeArrayOfProducts(benchmark::Stateamp; state) 
{
  for (auto _ : state) {
    std::vector<int> temp;
    temp.resize(state.range(0));
    benchmark::DoNotOptimize(arrayOfProducts(temp));
  }
}

BENCHMARK(TimeArrayOfProducts)
    ->RangeMultiplier(2)->Range(1<<8, 1<<12)->Complexity(benchmark::oN);

Кстати, то, что вы пытаетесь сделать, известно как частичная сумма, и вы можете переписать код как…

 #include <numeric>
// requires C  20
std::vector<int> arrayOfProducts2(const std::vector<int>amp; in) 
{
  std::vector<int> frd_sum;
  std::vector<int> bck_sum;
  std::vector<int> resu<
  frd_sum.resize(in.size());
  bck_sum.resize(in.size());
  result.resize(in.size());
  std::partial_sum(in.begin(), in.end(), frd_sum.begin());
  std::partial_sum(in.rbegin(), in.rend(), bck_sum.begin());
  std::transform(frd_sum.begin(), frd_sum.end(), bck_sum.begin(), result.begin(), [](int a, int b){return a*b;});
  return resu<
}

Что происходит быстрее, потому что…

  1. Он должен иметь O(n) сложность
  2. Многие чипы (Intel) имеют аппаратную оптимизацию для очень маленьких циклов.
Метки: