Witam serdecznie, zastanawiam się o jaką złożoność mógłbym się pokusić dysponując jedną tablicą, bądź wczytując po prostu kolejne wartości:
[bbone=CPP,2995]int T[7] = { 7, 2 , 1, 4, 3, 6, 5 };[/bbone]
Jeśli chciałbym zrobić tablicę lub też od razu zliczać całkowitą ilość (w tym przypadku sumaMniejszych = 6+1+1+1 = 9), która pod i-tym indeksem przechowuje ilość liczb mniejszych od wartości i-tej z tablicy T po prawej stronie! (bardzo ważne), a więc chciałbym uzyskać drugą tablicę o wartościach:
[bbone=CPP,2996]int A[7] = { 6, 1, 0, 1, 0, 1, 0};[/bbone]
Prosiłbym o pomoc, z góry dziękuje za sugestie 
-- Pn cze 01, 2015 7:01 pm --
Pomysł #1 dotyczący zliczenia sumy, zamiast tworzenia tablicy A.
Niech SUMA oznacza naszą zmienną, w której będziemy trzymać interesujący nas wynik.
Tworzymy sobie listę dwukierunkową z dostępem do pierwszego i ostatniego elementu, w której kolejne elementy będą większe lub równe poprzedniemu. Następnie wczytujemy po kolei kolejne liczby, jeśli w naszej liście istnieje liczba większa od wczytanej w danej chwili to przemieszczamy się od ostatniego elementu dopóki element w liście nie jest równy bądź mniejszy od naszego wczytanego.
Np: (wczytaliśmy już do listy 3 4 5), a następną wczytywaną liczbą jest 3. Istnieje w tablicy liczba większa od naszej - 5. Przemieszczamy się 5 -> 4 -> 3, następnie dołączamy naszą drugą trójkę to listy, a do SUMY dopisujemy (ilość elementów - przejścia, w tym przypadku 3-2=1), tak działy aż nie wczytamy wszystkich liczb.
Problem tkwi w tym, iż ten mój pomysł nie jest nawet bliski złożoności O(N), hmm...
