magistrsko delo
Abstract
Računanje časovne zahtevnosti sodi med osnovne naloge področja analize algoritmov, s katero želimo pridobiti funkcijo, ki nam za dano velikost problema napove, koliko časa se bo algoritem izvajal. Teoretična analiza je pogosto zahtevna, poleg tega ima še nekatere druge pomanjkljivosti, zato si lahko pomagamo z empirično analizo časovne zahtevnosti, na kar smo se osredotočili v tem delu. Razvili smo postopke, ki omogočajo analizo rezultatov meritev, torej podatkov, ki jih pridobimo z izvajanjem algoritmov na nalogah različnih velikosti. Analiza vrne ocenjen razred časovne zahtevnosti ter zapis funkcije v simbolični obliki. Razvili smo novo metodo za detekcijo slabih meritev, ki temelji na analizi zaporednih točk. Uvedli smo novo metriko za primerjavo algoritmov med seboj. Uporabili smo tudi nekaj novih pristopov k že znanim metodam ter vse skupaj vgradili v obstoječi sistem za avtomatsko analizo algoritmov.
Keywords
algoritmi;računska zahtevnost;empirična računska zahtevnost;genetski algoritmi;računalništvo;računalništvo in informatika;magisteriji;
Data
Language: |
Slovenian |
Year of publishing: |
2019 |
Typology: |
2.09 - Master's Thesis |
Organization: |
UL FRI - Faculty of Computer and Information Science |
Publisher: |
[M. Žugelj] |
UDC: |
004(043.2) |
COBISS: |
1538417859
|
Views: |
678 |
Downloads: |
171 |
Average score: |
0 (0 votes) |
Metadata: |
|
Other data
Secondary language: |
English |
Secondary title: |
Empirical analysis of the algorithm time complexity |
Secondary abstract: |
Time complexity is known as one of the principal tasks of algorithm analysis; the goal is to obtain a function which - for a given size of the problem - estimates how much time the algorithm execution will take. Theoretical analysis is often cumbersome and has other drawbacks as well. Thus, the empirical analysis of time complexity can be used, which is also the primary focus of this paper. We have developed procedures that allow us analysis of measurements - i.e. data -, which we obtain by running algorithms on problems of different sizes. The analysis provides us with an estimated time complexity class and function in symbolic form. We have developed a new method for detection of bad measurements, which is based on analysis of consecutive points, and introduced new metrics for algorithm comparison. A few new approaches were intertwined together with existing methods, which was then, all together, integrated in the existing system for automatic algorithm analysis. |
Secondary keywords: |
algorithms;computational complexity;empirical computational complexity;genetic algorithms;computer science;computer and information science;master's degree; |
Type (COBISS): |
Master's thesis/paper |
Study programme: |
1000471 |
Embargo end date (OpenAIRE): |
1970-01-01 |
Thesis comment: |
Univ. v Ljubljani, Fak. za računalništvo in informatiko |
Pages: |
68 str. |
ID: |
11260255 |