В чем разница между этими тремя алгоритмами на основе сложности времени? - PullRequest
Новая
       3

В чем разница между этими тремя алгоритмами на основе сложности времени?

0 голосов
/ 15 марта 2020

Все эти три алгоритма просто вычисляют сумму Массива размера 10. Здесь я немного запутался между сложностью времени и тем, что хотел бы выбрать, какой из них быстрее. Можете ли вы помочь мне, чтобы я мог хорошо понять сложность времени.

Al go 1
В алгоритме 1 l oop выполняется 10 раз. 

int arr[10] = {1, 2, 3, 4, 5 ,6 ,7, 8, 9, 10};
int sum = 0;
int size = 10;
int i = 0;
for(int i = 0; i < size; i++){
    sum += arr[i];
}
cout<<sum;

Al go 2
В алгоритме 2 l oop выполняется в половину от размера массива, но на каждой итерации выполняет двойное число операций. Уменьшение числа итераций сделает алгоритм еще быстрее? 

int arr[10] = {1, 2, 3, 4, 5 ,6 ,7, 8, 9, 10};
int sum = 0;
int size = 10;
int i = 0;
for(int i = 0; i < size/2; i++){
    sum += arr[i];
    sum += arr[size-1-i];
}
cout<<sum;

Al go 3 

int arr[10] = {1, 2, 3, 4, 5 ,6 ,7, 8, 9, 10};
int sum = 0;
int size = 10;
int i = 0;

for(i = 0; i < size/2; i++){
    sum += arr[i];
}

for(int j = i; j < size; j++){
    sum += arr[j];
}
cout<<sum;

Ответы [ 3 ]

1 голос
/ 16 марта 2020

Здесь кажется, что приблизительное время для всех трех кодов разное, потому что l oop выполняется разное количество раз n и n / 2. Но когда мы go в его мелких деталях, то видно, что число Выполнение оператора такое же ..

В первом 

1 in loop;
loop runs n times;
total=n;

Во втором 

2 in loop; 
loop runs n/2 times;
total n

В третьем 

   1 in first loop;
   loop runs n/2 times;
   total for first is n/2;
   similarly in second ;
   total n

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

1 голос
/ 15 марта 2020

Краткий ответ: Все они имеют одинаковую сложность времени, O (n).

С точки зрения сложности времени (обозначение big-oh) все они одинаковы.

Первый выполняет (one operation * size of array), что составляет O(n) сложность (учитывая n - размер массива).
Второй выполняет (2 operations * (size of array) / 2), что составляет O(2 * n / 2), что также O(n).
Третий выполняет (1 operation * size of array / 2 + 1 operation * size of array / 2), что также O(n).

3 алгоритма могут незначительно отличаться в режиме реального времени, но это связано с оптимизацией кэша и связанными темами.

0 голосов
/ 15 марта 2020

Как упоминалось ранее, все алгоритмы имеют O(n) сложность. Но время выполнения может варьироваться.

Есть удобный сервис Quick C ++ Bechmark . Я протестировал 4 алгоритма, используя следующий код 

#include <array>
#include <numeric>
constexpr int SIZE = 10000;
std::array<int, SIZE> arr;

static void algo1(benchmark::State& state) {
  std::iota(begin(arr), end(arr), 0);
  for (auto _ : state) {
    int sum = 0;
    for(int i = 0; i < SIZE; i++){
        sum += arr[i];
    }
    benchmark::DoNotOptimize(sum);
  }

}
BENCHMARK(algo1);
static void algo2(benchmark::State& state) {
  std::iota(begin(arr), end(arr), 0);
  for (auto _ : state) {
    int sum = 0;
    for(int i = 0; i < SIZE/2; i++){
        sum += arr[i];
        sum += arr[SIZE-1-i];
    }
    benchmark::DoNotOptimize(sum);
  }
}
BENCHMARK(algo2);
static void algo3(benchmark::State& state) {
  std::iota(begin(arr), end(arr), 0);
  for (auto _ : state) {
    int sum = 0, i;
    for(i = 0; i < SIZE/2; i++){ sum += arr[i]; }
    for(int j = i; j < SIZE; j++){ sum += arr[j]; }
    benchmark::DoNotOptimize(sum);
  }
}
BENCHMARK(algo3);
static void algo4(benchmark::State& state) {
  std::iota(begin(arr), end(arr), 0);
  int sum;
  for (auto _ : state) {
    sum = std::accumulate(begin(arr), end(arr), 0);
    benchmark::DoNotOptimize(sum);
  }  
}
BENCHMARK(algo4);

The results are:
algo1: 2770
algo2: 2913
algo3: 2782
algo4: 2770

Резюме: algo2 немного медленнее, algo1, algo3, algo4 имеют одинаковое время выполнения.

...