Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 7 of 7 for “"Amortized complexity"”.
-
Using Application Benefit for Proactive Resource Allocation in Asynchronous Real-Time Distributed Systems
… in a much faster way. RBA* incurs a quadratic amortized complexity in terms of subtask arrivals for the most computationally intensive component when DASA is used as the underlying process-scheduling algorithm, whereas OBA incurs a logarithmic amortized complexity for the corresponding …
-
High performance sequential and lock-free parallel access priority queue structures
… that Twol-based EDPQs have constant-A? O(1) amortized complexity, where A? is the mean of jump of event distribution. For the parallel access domain, we extend the sequential Twol structure to derive a novel lock-free Twol priority queue which is the first multi-tier multi-bucket structure …
-
THE DESIGN AND ANALYSIS OF HEAP ALGORITHMS
… used are relaxation in heap order and the use of amortized analysis. The structure is semi-implicit due to the use of 1 extra bit per node to maintain heap order and the allowance of some systematically controlled extra space. Using amortized analysis, several improved time bounds are derived. …
-
Statická analýza v nástroji Facebook Infer zaměřená na analýzu výkonnosti
Statická analýza se v současnosti dostává do popředí v oblasti technik pro odhalování chyb v moderním software. Nedostatečná škálovatelnost, především v kombinaci se zachováním potřebné přesnosti, je však přetrvávající problém u většiny současných nástrojů pro statickou analýzu, což je činí …
-
Zdokonalená analýza výkonnosti v nástroji Looper
Náš nástroj REBEL je statický analýzátor pro odvozování co nejtěsnějších horních mezí ceny vykonávání imperativních nerekurzivních programů. REBEL je nástupcem nástroje Looper v2. Oba nástroje REBEL a Looper v2 jsou reimplementací nástroje LOOPUS, který využívá model programu zvaný zvaný difference …
-
Automaty v rozhodovacích procedurách a výkonnostní analýze
Tato práce se věnuje vylepšení současného stavu formalní analýzy a verifikace založené na automatech a zaměřené na systémy s nekonečnými stavovými prostory. V první části se práce zabývá dvěma rozhodovacími procedurami pro logiku WS1S, které jsou založené na korespondenci mezi formulemi logiky WS1S …
-
Αποτελεσματικοί αλγόριθμοι και βελτιωμένες τεχνικές αναζήτησης χωρικής, χρονικής και χώρο-χρονικής πληροφορίας
… known performance in terms of time and space complexity, for both static and dynamic problems. Our new result studies the static 2D range query problem and an extension of the most well-known technique for static range queries of higher dimensions. At the end of this chapter, we describe the …