Porównanie wszystkich elementów tablicy - algorytm C

Question

Mam macierz m * n i dla każdego wiersza muszę porównać wszystkie elementy między nimi. Dla każdej pary, którą znajdę, zadzwonię do funkcji, która wykona pewne obliczenia.

przykład:

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 

Stosując C Napisałem:

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

      //Do something 
     } 
    } 
} 

ja zastanawiać, czy można użyć algorytmu z mniejszą złożoność.

Answer 1

Nie, to O (n^2) z definicji [zbyt długo tu wyjaśnić, ale uwierzcie mi (-:]
Ale można zmniejszyć liczbę iteracji o połowę:

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

Nie, można uzyskać tylko niższą złożoność obliczeniową, jeśli uwzględnimy wiedzę dotyczącą zawartości tablicy i semantykę operacji, aby zoptymalizować algorytm.

Answer 3

Nie jest kilka rzeczy, które możesz zrobić, ale które są możliwe, a które nie zależą od natury tablicy i zastosowanej formuły. Ogólna złożoność prawdopodobnie pozostanie niezmieniona lub nawet się zwiększy, nawet jeśli obliczenia można przyspieszyć, chyba że formuła ma Zależność złożoności od jej argumentów, w którym to przypadku można uzyskać zmniejszenie złożoności.

Również przejście od AO (N^a) do BO (N^b) z b> a (większa złożoność) może być nadal warte zainteresowania, dla pewnego zakresu N, jeśli B jest dostatecznie mniejsze niż A.

w przypadkowej kolejności:

• jeśli matryca ma kilka powtarzane elementy, może być korzystne aby stosować funkcję buforowania:

  funkcji wynik (arg1, arg2) { int i = index (arg1, arg2); // W zależności od wartości, może to być // coś takiego jak arg1 * (MAX_ARG2 + 1) + arg2; if (! Stored [i]) {// stored i wartości są przydzielane i inicjowane // gdzie indziej - lub w tej funkcji przy użyciu flagi statycznej. zapisane [i] = 1; wartości [i] = true_function (arg1, arg2); } zwraca wartości [i]; }

  Następnie masz narzut pamięci proporcjonalny do liczby różnych par dostępnych wartości. Koszt narzutowy może wynosić O (| arg1 | * | arg2 |), ale w pewnych okolicznościach (np. true_function() jest kosztowny) oszczędności z nawiązką skompensują dodatkową złożoność.

  • ścięcie wzoru na części (niemożliwe do co wzorze) i wyrazić jako:

    F (x, y) = G (x) IO H (r) op J (X , y)

  , następnie można wykonać cykl O (max (M, N)), obliczając wstępnie G [] i H []. To również ma koszt pamięci O (M + N). Jest to wygodne tylko wtedy, gdy obliczeniowa różnica wydatków między F i J jest znaczna. Albo można zrobić:

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

  który przynosi trochę złożoności z O (n^2) w dół do O (n).

  • pierwsze dwie metody są użyteczne w tandemie jeśli G() lub H() są praktyczne w buforze (ograniczonym zakresie argumentów, drogi funkcja).

  • znajdź "prawo" do połączenia F (a, b) z F (a + c, b + d). Następnie można uruchomić algorytm buforowania o wiele bardziej efektywnie, ponownie wykorzystując te same obliczenia. Przesuwa to pewną złożoność z O (N^2) do O (N) lub nawet O (log N), tak że podczas gdy całkowity koszt jest nadal kwadratowy, rośnie znacznie wolniej, a wyższe ograniczenie dla N staje się praktyczne. Jeśli F jest samo w sobie złożonością wyższą niż stała w (a, b), może to również zmniejszyć tę kolejność (jako skrajny przykład, przypuśćmy, że F jest iteracyjne w a i/lub b).