- Tytuł:
-
Maximum subarray problem optimization for specific data
Optymalizacja problemu największej podtablicy dla specyficznych danych - Autorzy:
- Rojek, T.
- Powiązania:
- https://bibliotekanauki.pl/articles/407746.pdf
- Data publikacji:
- 2017
- Wydawca:
- Politechnika Lubelska. Wydawnictwo Politechniki Lubelskiej
- Tematy:
-
algorithm design and analysis
maximum subarray problem
Kadane’s algorithm
optimization
analiza algorytmów
projektowanie algorytmów
problem maksymalnej podtablicy
algorytm Kadane
optymalizacja - Opis:
-
The maximum subarray problem (MSP) is to the find maximum contiguous sum in an array. This paper describes a method of Kadanes algorithm
(the state of the art) optimization for specific data (continuous sequences of zeros or negative real numbers). When the data are unfavourable, the
modification of the algorithm causes a non significant performance loss (1% > decrease in performance). The modification does not improve time
complexity but reduces the number of elementary operations. Various experimental data sets have been used to evaluate possible time efficiency
improvement. For the most favourable data sets an increase in efficiency of 25% can be achieved.
Problem najwiekszej podtablicy to inaczej znalezienie podciągu, którego suma na największą wartość. Artykuł opisuje optymalizację algorytmu Kadane dla specyficznych danych (z powtarzającymi się ciągami zer lub liczb negatywnych). W przypadku niekorzystnych danych wejściowych zaproponowa modyfikacja nieznacznie spowalnia działanie algorytmu (mniej niż 1% szybkości działania). Ulepszenie algorytmu nie zmienia rzędu asymptotycznego tempa wzrostu, lecz zmniejsza ilość elementarnych operacji. Eksperymenty wykazały, że dla sprzyjających danych możemy zmniejszyć efektywny czas działania algorytmu o 25%. - Źródło:
-
Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Środowiska; 2017, 7, 4; 62-65
2083-0157
2391-6761 - Pojawia się w:
- Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Środowiska
- Dostawca treści:
- Biblioteka Nauki
Artykuł