Часто встречающиеся "неправильные" алгоритмы

Имеем: 10 примеров неправильных (точней, сильно избыточно программируемых) алгоритмов.

Требуется: реализовать алгоритмы так, чтобы их временная сложность соответствовала требуемой в постановке задачи или были проведены иные оптимизации.

Это не каверзные вопросы, и даже не популярные ошибки, это гораздо проще :) Но на основе этих примеров можно увидеть много других распространённых "излишеств" в коде начинающих.

Ответов в этой статье нет, попробуйте найти их сами.

1. Выбор элементов главной диагонали квадратной матрицы A[n,n]

for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
 if (i==j) cout << a[i][j] << “ “;

Очень плохо, что здесь сложность O(n²). Сделайте O(n)

2. Сортировка элементов вектора a[n] по возрастанию

for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
 if (a[i]>a[j]) {
  int t=a[i]; a[i]=a[j]; a[j]=t;
 }

Даже при столь примитивной "пузырькообразной" сортировке, количество операций можно уменьшить как минимум вдвое - от O(n²) до ~O(n²/2), а как?

3. Поиск номера (индекса) максимального элемента в массиве a[n]

int max=a[0], imax=0;
for (int i=1; i<n; i++) 
 if (a[i]>max) {
 max = a[i]; imax=i; 
}

Алгоритм даже проще реализовать без использования двух дополнительных переменных:

#include <iostream>
using namespace std;

int main() {
 const int n = 5;
 int a[n] = {1,4,5,3,2};
 
 int imax = 0;
 for (int i = 0; i < n; i++) if (a[i] > a[imax]) imax = i;
  
 cout << "Index=" << imax;
 cin.get(); return 0;
}

4. Обработка (или вывод) всех элементов симметрической относительно главной диагонали квадратной матрицы A[n,n]

for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
 if (i==j) cout << a[i][j] << " " << a[j][i] << enl;

Как и в задаче 2, можно сократить число шагов вложенного цикла хотя бы вдвое.

5.Определение количества минимальных элементов в целочисленном массиве A[n]

int min=a[0], k=0;
for (int i=1; i<n; i++)
 if (a[i]<min) min=a[i];
for (int i=0; i<n; i++)
 if (a[i]==min) k++;

От O(2*n) легко можно перейти к O(n), выполнив работу за один цикл.

6. Поиск суммы элементов последовательности вида n , 2*n, …, m*n

double s=0; int n=3, m=10;
for (int i=1; i<=m; i++) 
 s+=i*n;

Здесь не нужен цикл вообще, даже сложности O(n). Разумеется, есть решение O(1).

7. Вычисление суммы степенного ряда вида 1+x+x²+…+xⁿ

double sum=0, x=0.5;
for (int i=0; i<=n; i++)
 sum += pow(x,i);

Не стоит так понижать точность расчёта, заново вычисляя всё большую степень от x на каждом шаге цикла.

Попробуйте реализовать алгоритм без необходимости нового полного расчёта степени на каждом шаге.

8. Получение четырёхзначного натурального числа из пары двузначных

int a=12,b=34;
char buf[4];
itoa(a,buf,10);
itoa(b, &buf[2], 10);
cout << buf;

Дополнительный строковый буфер совершенно ни к чему, достаточно арифметики.

9. Поиск в матрице натуральных чисел, строки и столбцы которой упорядочены по возрастанию, элемента со значением find

const int n=4,m=3;
int a[n][m]={
  {10,20,30},
  {15,35,40},
  {20,55,60},
  {40,80,90}
};
 int find = 55;
 bool found = false;
 for (int i=0; i<n; i++)
 for (int j=0; j<m; j++) {
  if (a[i][j]==find) {
   found = true; break;
  }
 }

Плохо, что дополнительная информация об упорядоченности элементов никак не используется при поиске.

Попробуйте решить эту задачу за время, меньшее, чем O(n²), желательно, за логарифмическое.

10. Поиск в массиве натуральных чисел a[n] пары элементов со значениями item1 и item2, расстояние между которыми минимально

const int n=10;
 int a[n] = {
  3,5,10,8,4,12,5,3,0,7
 };
 int item1=3,item2=8,min=n;
 for (int i=0; i<n; i++)
 for (int j=0; j<n; j++) {
  if (a[i]==item1 && a[j]==item2 && abs(i-j)<min) {
      min = abs(i-j);
  }
 }
 cout << min;

Здесь уж сам Бог велел перейти от O(n²) к O(n)

03.06.2018, 23:32 [2518 просмотров]