Сравнение всех элементов массива - алгоритм C

Question

У меня есть матрица m * n и для каждой строки мне нужно сравнить все элементы из них. Для каждой пары, которую я нахожу, я вызову функцию, которая будет выполнять некоторые вычисления.

Пример:

my_array -> {1, 2, 3, 4, 5, ...} 

I take 1 and I have: (1,2)(1,3)(1,4)(1,5) 
I take 2 and I have: (2,1)(2,3)(2,4)(2,5) 
and so on 

Используя C Я написал это:

for (i=0; i<array_length; i++) { 
    for (k=0; k<array_length; k++) { 
     if (i==k) continue; 

      //Do something 
     } 
    } 
} 

мне было интересно, если я могу использовать алгоритм с меньшей сложностью.

Answer 1

Нет, это O (N^2) по определению [слишком долго объяснять здесь, но поверьте мне (-:]
Но вы можете уменьшить количество итераций наполовину:

for (i=0; i<array_length; i++) { 
    for (k=i+1; k<array_length; k++) { // <-- no need to check the values before "i" 
      //Do something 
      //If the order of i and k make a different then here you should: 
      //'Do something' for (i,k) and 'Do something' for (k,i) 
     } 
    } 
} 

Answer 2

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

Answer 3

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

Кроме того, переход от AO (N^a) к BO (N^b) с b> a (более высокая сложность) может быть оправданным для некоторого диапазона N, если B достаточно меньше A.

в частности, нет порядка:

• , если матрица имеет несколько повторен элементов, это может быть удобно использовать функцию кэширования:

  результата функции (arg1, arg2) { INT I = индекс (arg1, arg2); // В зависимости от значений это может быть // что-то вроде arg1 * (MAX_ARG2 + 1) + arg2; if (! Stored [i]) {// сохранены и значения выделены и инициализированы // в другом месте - или в этой функции с использованием знака статического значения //. сохранено [i] = 1; значения [i] = true_function (arg1, arg2); } значения возврата [i]; }

  Затем у вас есть накладные расходы памяти, пропорциональные количеству различных пар доступных значений. Накладные расходы могут быть O (| arg1 | * | arg2 |), но в некоторых случаях (например, true_function() стоит дорого), экономия будет более чем компенсировать дополнительную сложность.

  • нарезать формулу на куски (не возможно для каждый формулы) и выражают его как:

    F (х, у) = G (х) оп Н (у) оп J (х , y)

  Затем вы можете выполнить предварительный расчет O (max (M, N)) G [] и H []. Это также имеет стоимость памяти O (M + N). Это удобно, только если разница между расходами между F и J значительна. Или вы могли бы сделать:

  for (i in 0..N) { 
      g = G(array[i]); 
      for (j in 0..N) { 
       if (i != j) { 
        result = f(array[i], array[j], g); 
       } 
      } 
  } 
  

  который приносит некоторые о сложности из O (N^2) вплоть до O (N).

  • первых два метод является полезным в тандеме, если G() или Н() практичны в кэш (ограниченный диапазон аргумента функции дорого).

  • найти «закон» для связывания F (a, b) с F (a + c, b + d). Тогда вы можете запустить алгоритм кэширования гораздо более эффективно, повторно используя одни и те же вычисления. Это сдвигает некоторую сложность от O (N^2) до O (N) или даже O (log N), так что, хотя общая стоимость по-прежнему квадратична, она растет намного медленнее, и более высокая оценка для N становится практичной. Если F само имеет более высокий порядок сложности, чем константа в (a, b), это также может уменьшить этот порядок (в качестве крайнего примера предположим, что F является итеративным по a и/или b).