OPTYMALIZACJA PROBLEMU NAJWIĘKSZEJ PODTABLICY DLA SPECYFICZNYCH DANYCH

##plugins.themes.bootstrap3.article.sidebar##

pdf (angielski)
Opublikowane: 2017-12-21
DOI: https://doi.org/10.5604/01.3001.0010.7507
Crossref
Scopus
Google Scholar
Europe PMC

Archiwum

2017

##plugins.themes.bootstrap3.article.main##

Authors

Tomasz Rojek

trojek@pk.edu.pl

Cracow University of Technology, Faculty of Mechanical Engineering, Institute of Applied Informatics

Abstrakt

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%.

Słowa kluczowe:

analiza i projektowanie algorytmów, problem maksymalnej podtablicy, algorytm Kadane, optymalizacja

Bibliografia

##plugins.themes.bootstrap3.article.details##

OPTYMALIZACJA PROBLEMU NAJWIĘKSZEJ PODTABLICY DLA SPECYFICZNYCH DANYCH. (2017). Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Środowiska, 7(4), 62-65. https://doi.org/10.5604/01.3001.0010.7507