Każdy pomysł na przekształcenie tego O (n^2) algo w O (n)

Question

Mam następujący algorytm, który skanuje dużą okrągłą tablicę (dane). W pewnym momencie tablicy muszę przyjrzeć się wartościom z przeszłości (0 = najnowszy punkt danych, n = najstarszy punkt danych) i określić, czy była wartość 5% poniżej bieżącej wartości. W końcu napisałem algorytm O (n^2), który działa dobrze, ale nie jest to skalowalne.

 const int numberOfDataPointsInPast = 1000; 
     int numberOfDataPoints = 0; 
     for (int i = numberOfDataPointsInPast; i >= 0; i--) 
     { 
      double targetPoint = data[i] * 0.95; 
      for (int j = i + numberOfDataPointsInPast; j > i; j--) 
      { 
       if (data[j] <= targetPoint) 
       { 
        numberOfDataPoints++; 
        break; 
       } 
      } 
     } 

Jakiś pomysł, w jaki sposób mogę to przekształcić w O (n) algo? Dzięki!

Answer 1

Podczas iteracji tablicy przechowuj najniższą wartość. Wymaga to utworzenia zmiennej min i wykonania sprawdzenia porównania w każdym kroku. Zamiast porównywać wszystkie poprzednie wartości z nowym, porównaj je tylko z najniższymi.

Answer 2

EDIT:

Po tym myśleć somemore, łatwym O (n) algorytm czas jest to możliwe, bez potrzeby RMQ lub drzewa (patrz poprzednia część mojej odpowiedzi poniżej).

Biorąc tablicę A [1 ... n] i szerokość okna W, należy znaleźć minimum A [i, ... i + W], biorąc pod uwagę, i.

W tym celu wykonaj następujące czynności.

Podziel A [1 ... n] na sąsiednie bloki o rozmiarze W-1. B1, B2, ... B (W-1).

Dla każdego bloku B należy zachować jeszcze dwa bloki o nazwach BStart i BEnd.

BStart [i] = minimum B 1, B [2], ..., B [i].

BEnd [i] = minimum B [W-1], B [W-2], ..., B [W-1].

Można to zrobić w czasie O (W) dla każdego bloku, a więc O (n) całkowitego czasu.

Teraz podana wartość i, tablica podrzędna A [i ... i + W] będzie obejmowała dwa kolejne bloki, na przykład B1 i B2.

Znajdź minimum od i do końca bloku B1 i rozpocznij blok B2 do i + w, używając odpowiednio B1End i B2Start.

To jest czas O (1), więc całkowite O (n).

kolistego tablicy C [1 .... n] Wszystko, co trzeba zrobić, to uruchomić powyżej na

A [2n .... 1], który jest w zasadzie dwie kopie C łączone razem tj [1 ... n] = C [1 ... n] oraz [n + 1 ... 2 n] = C [1 ... n]

---

Poprzednie writeup.

Ok. Zakładając, że tym razem dobrze zrozumiałem twoje pytanie ...

Jest to możliwe w czasie O (n) i O (n).

W rzeczywistości istnieje możliwość zmiany rozmiaru okna na dowolną liczbę, która ma być różna dla różnych elementów i nadal działa!

Otrzymano tablicę A [1 ...n], może być wstępnie przetworzony w przestrzeni O (n) i O (n), aby odpowiedzieć na pytania w formularzu: What is the position of a minimum element in the sub-array A[i...j]? w stała czas!

Nazywa się to problemem o numerze Range Minimum Query.

Teoretycznie można to zrobić w czasie O (n).

Wystarczy użyć drzewa, aby uzyskać czas O (nlogW), gdzie W jest wielkością okna i prawdopodobnie będzie działało znacznie lepiej niż RMQ, w praktyce, ponieważ oczekuję, że ukryte stałe mogą pogorszyć RMQ.

Możesz użyć drzewa w następujący sposób.

Zacznij od tyłu i wstaw elementy W. Znajdź minimum i wciśnij na stos. Teraz usuń pierwszy element i wstaw (W + 1) th element. Znajdź minimum, naciśnij stos.

Kontynuuj w ten sposób. Całkowity czas przetwarzania będzie wynosił O (nlogW).

Na końcu masz stos minimów, które możesz po prostu odpaść, gdy będziesz teraz chodził po tablicy drugi raz, tym razem we właściwej kolejności, szukając 0,95 * celu.

Ponadto, twoje pytanie nie jest całkiem jasne, mówisz, że jest to bufor cykliczny, ale wydaje się, że nie robisz operacji modulus z długością. I tak jak zakodowany, twój algorytm to O (n), nie O (n^2), ponieważ rozmiar twojego okna jest stały.

Answer 3

Nie sądzę, że można to zrobić w O (n), ponieważ rozwiązując go przy pomocy O (n), można go posortować za pomocą O (n), a to nie jest możliwe. (minimum, dla sortowania jest O (nlogn)).

EDIT - zmniejszenie sortowania tego problemu

Załóżmy, można powiedzieć, dla każdego punktu, jak wiele punktów w przeszłości wartość mniejsza niż x% (tutaj x wynosi 5 - ale x może być także 0 to liczyć będą wszelkie mniejsze punkty w przeszłości).

Teraz - załóżmy, że chcesz posortować tablicę n elementów.
Jeśli można uzyskać liczbę mniejszych punktów w przeszłości dla wszystkich elementów w O (n), jeśli punkt a ma większą wartość niż punkt b, liczba dla punktu a będzie również większa niż liczba dla punktu b (ponieważ tablica jest okrągła). Tak więc ten problem faktycznie daje funkcję od wartości do liczby, która zachowuje kolejność.
Teraz - nowe wartości są powiązane między o i n, co można posortować w czasie n.

Popraw mnie, jeśli się mylę (być może dlatego, że nie zrozumiałem problemu w pierwszej kolejności).

Answer 4

Możesz wziąć pierwszą numberOfDataPointsInPast w przeszłości, posortuj je, czyli n log (n). Następnie wykonaj wyszukiwanie binarne, log (n), znajdź najniższy punkt danych, który przejdzie test 5%. Dzięki temu dowiesz się, ile punktów z numberOfDataPointsInPast zda test w n. log (n), w którą wierzę.

Answer 5

Możesz zachować tablicę buffArray dla elementów, która będzie zawierać bieżące elementy "okna" posortowane w porządku rosnącym.

Dla każdej iteracji:

• Sprawdź, czy bieżący element jest niższa niż 0.95 * buffArray[0] i wykonać niezbędne działania, jeśli jest.
• Usuń element, który wychodzi z "okna" (tj. i+numberOfDataPointsInPast "th") z buffArray.
• Dodaj nowy element (tj. i 'th) do buffArray zachowując kolejność sortowania.

To nie jest O (N), jak rozumiem, ale zdecydowanie bardziej efektywne niż O (N^2), ponieważ dodawanie i usuwanie elementów do/z posortowanej tablicy to O (log N). Podejrzewam, że końcowa wydajność to O (N log (W)), gdzie W to numberOfDataPointsInPast.

Answer 6

myślę zrozumieć wymagania .... Mam zamiar przekształcić problem:

Biorąc: przesuwne rozmiar bufora K i tablicę danych rozmiaru n> K, indeksy od 0 do N-1.

Oblicz: policzyć liczbę punktów j takie K < = J < N-1, i zestaw {danych [j -1], dane [J-2], dane [J-3], ... dane [jK]} zawierają co najmniej jeden punkt o wartości < = 0,95 * danych [j].

Można to osiągnąć w następujący sposób:

1. Sortowanie punkty {danych [0], danych [1], ... danych [K1]} pomocą struktury danych, które w większości O (log N) koszt wstawienia/usunięcia.

2. inicjalizacji licznika R, 0 ° C, aby zainicjować j K.

3. kontrolę posortowanej tablicy, czy najniższy punkt jest < = danych [j] * 0,95; jeśli tak, przyrost R.

4. Usuń dane [j-K] z posortowanej tablicy i wstaw dane [j] do posortowanej tablicy.

5. Przyrost j

6. Jeśli j < N, wróć do kroku 3.

Kluczem tutaj jest, aby wybrać właściwą strukturę danych. Jestem prawie pewien, że binarne drzewo zadziałałoby. Jeśli koszt inkrementalnego wstawienia wynosi O (log N), całkowity czas działania to O (N log N).

Answer 7

Powtórzenia należy rozpoczynać od dołu i zwiększać (zachowując min przeszłość). W tej chwili, jak napisano, algorytm zawsze patrzy wstecz, zamiast iść naprzód i pamiętać o minionym minimum.

Po dodaniu nowych punktów zakres punktów danych może tylko zwiększyć górną lub dolną granicę. Gdy dolna granica zmniejsza się, utrzymanie dolnej granicy jest wszystkim, co jest konieczne. Wszelkie nowe punkty, które są większe niż dolna granica/0.95 będzie do zaakceptowania (ponieważ dolna granica jest zawsze w przeszłości):

const int numberOfDataPointsInPast = 1000; 
int numberOfDataPoints = 0; 
double lb = NAN; 
for (int i = 0; i < numberOfDataPointsInPast; i++) 
{ 
    if (lb == NAN || data[i] < lb) { 
     lb = data[i]; 
    } 
    if (data[i] >= lb/0.95) { 
     numberOfDataPoints++ 
    } 
} 

Answer 8

Spróbuj tego:

Zawsze utrzymywać dwa wskaźniki do elementów w swoim buforze. Jedna jest minimalną wartością napotkaną, a druga jest następną mimumum (która jest kolejną największa z przyrostem). Pamiętaj, że są to wskaźniki do bufora.

Na każdym etapie przechodzenia przez bufor określ, czy bieżąca wartość jest mniejsza lub równa wartości wskazanej przez min1 lub min2, jeśli tak, zaktualizuj min1 lub min2, aby wskazać bieżącą lokalizację. W przeciwnym razie, jeśli przez arytmetykę wskaźnika, wartość min1 lub min2 wynosi 1500 z powrotem w buforze, musisz określić, który to jest i ponownie dostosować min1 lub min2 odpowiednio, to jest min1 punktów do min2, a min2 jest ustawione na punkt w obecnej lokalizacji lub min2 jest po prostu ustawione na wskazywanie aktualnej lokalizacji.

czy wartość wskazywanego przez którąkolwiek MIN1 lub min2 jest mniejsza niż 15% obecnej wartości mogą następnie być określona przez proste porównanie ...

Answer 9

Masz dwie możliwości:

1. Sortuj it - O (n log n)

2. Median of Medians algorithm