Einloggen

Thematische Bibliographien / Amortized complexity

Inhaltsverzeichnis

Zeitschriftenartikel
Bücher
Buchteile
Konferenzberichte

Auswahl der wissenschaftlichen Literatur zum Thema „Amortized complexity“

Autor: Grafiati

Veröffentlicht am 28. Juni 2021

Zuletzt aktualisiert am 11. Februar 2022

Geben Sie eine Quelle nach APA, MLA, Chicago, Harvard und anderen Zitierweisen an

Wählen Sie eine Art der Quelle aus:

Machen Sie sich mit den Listen der aktuellen Artikel, Bücher, Dissertationen, Berichten und anderer wissenschaftlichen Quellen zum Thema "Amortized complexity" bekannt.

Neben jedem Werk im Literaturverzeichnis ist die Option "Zur Bibliographie hinzufügen" verfügbar. Nutzen Sie sie, wird Ihre bibliographische Angabe des gewählten Werkes nach der nötigen Zitierweise (APA, MLA, Harvard, Chicago, Vancouver usw.) automatisch gestaltet.

Sie können auch den vollen Text der wissenschaftlichen Publikation im PDF-Format herunterladen und eine Online-Annotation der Arbeit lesen, wenn die relevanten Parameter in den Metadaten verfügbar sind.

Zeitschriftenartikel zum Thema "Amortized complexity"

1

Tarjan, Robert Endre. „Amortized Computational Complexity“. SIAM Journal on Algebraic Discrete Methods 6, Nr. 2 (April 1985): 306–18. http://dx.doi.org/10.1137/0606031.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

2

Feder, Tomás, Eyal Kushilevitz, Moni Naor und Noam Nisan. „Amortized Communication Complexity“. SIAM Journal on Computing 24, Nr. 4 (August 1995): 736–50. http://dx.doi.org/10.1137/s0097539792235864.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

3

Nipkow, Tobias, und Hauke Brinkop. „Amortized Complexity Verified“. Journal of Automated Reasoning 62, Nr. 3 (13.03.2018): 367–91. http://dx.doi.org/10.1007/s10817-018-9459-3.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

4

Kingston, Jeffrey H. „The amortized complexity of Henriksen's algorithm“. BIT 26, Nr. 2 (Juni 1986): 156–63. http://dx.doi.org/10.1007/bf01933741.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

5

Bahendwar, Isha Ashish, Ruchit Purshottam Bhardwaj und Prof S. G. Mundada. „Amortized Complexity Analysis for Red-Black Trees and Splay Trees“. International Journal of Innovative Research in Computer Science & Technology 6, Nr. 6 (November 2018): 121–28. http://dx.doi.org/10.21276/ijircst.2018.6.6.2.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

6

Cramer, Ronald, Ivan Damgård und Marcel Keller. „On the Amortized Complexity of Zero-Knowledge Protocols“. Journal of Cryptology 27, Nr. 2 (31.01.2013): 284–316. http://dx.doi.org/10.1007/s00145-013-9145-x.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

7

NAVARRO, GONZALO, RODRIGO PAREDES, PATRICIO V. POBLETE und PETER SANDERS. „STRONGER QUICKHEAPS“. International Journal of Foundations of Computer Science 22, Nr. 04 (Juni 2011): 945–69. http://dx.doi.org/10.1142/s0129054111008507.

Der volle Inhalt der Quelle

Annotation:

The Quickheap (QH) is a recent data structure for implementing priority queues which has proved to be simple and efficient in practice. It has also been shown to offer logarithmic expected amortized complexity for all of its operations. Yet, this complexity holds only when keys inserted and deleted are uniformly distributed over the current set of keys. This assumption is in many cases difficult to verify, and does not hold in some important applications such as implementing some minimum spanning tree algorithms using priority queues. In this paper we introduce an elegant model called a Leftmost Skeleton Tree (LST) that reveals the connection between QHs and randomized binary search trees, and allows us to define Randomized QHs. We prove that these offer logarithmic expected amortized complexity for all operations regardless of the input distribution. We also use LSTs in connection to α-balanced trees to achieve a practical α-Balanced QH that offers worst-case amortized logarithmic time bounds for all the operations. Both variants are much more robust than the original QHs. We show experimentally that randomized QHs behave almost as efficiently as QHs on random inputs, and that they retain their good performance on inputs where that of QHs degrades.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

8

Hiary, Ghaith A. „An amortized-complexity method to compute the Riemann zeta function“. Mathematics of Computation 80, Nr. 275 (25.01.2011): 1785–96. http://dx.doi.org/10.1090/s0025-5718-2011-02452-x.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

9

Hoogerwoord, Rob R. „Functional Pearls A symmetric set of efficient list operations“. Journal of Functional Programming 2, Nr. 4 (Oktober 1992): 505–13. http://dx.doi.org/10.1017/s0956796800000526.

Der volle Inhalt der Quelle

Annotation:

In this paper we show that it is possible to implement a symmetric set of finite-list operations efficiently; the set is symmetric in the sense that lists can be manipulated at either end. We derive the definitions of these operations from their specifications by calculation. The operations have O(1) time complexity, provided that we content ourselves with, so-called, amortized efficiency, instead of worst-case efficiency

APA, Harvard, Vancouver, ISO und andere Zitierweisen

10

Dumitrescu, Adrian. „A Selectable Sloppy Heap“. Algorithms 12, Nr. 3 (06.03.2019): 58. http://dx.doi.org/10.3390/a12030058.

Der volle Inhalt der Quelle

Annotation:

We study the selection problem, namely that of computing the ith order statistic of n given elements. Here we offer a data structure called selectable sloppy heap that handles a dynamic version in which upon request (i) a new element is inserted or (ii) an element of a prescribed quantile group is deleted from the data structure. Each operation is executed in constant time—and is thus independent of n (the number of elements stored in the data structure)—provided that the number of quantile groups is fixed. This is the first result of this kind accommodating both insertion and deletion in constant time. As such, our data structure outperforms the soft heap data structure of Chazelle (which only offers constant amortized complexity for a fixed error rate 0 < ε ≤ 1 / 2 ) in applications such as dynamic percentile maintenance. The design demonstrates how slowing down a certain computation can speed up the data structure. The method described here is likely to have further impact in the field of data structure design in extending asymptotic amortized upper bounds to same formula asymptotic worst-case bounds.

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Mehr Quellen

Bücher zum Thema "Amortized complexity"

1

Sundar, R. Amortized complexity of data structures. New York: Courant Institute of Mathematical Sciences, New York University, 1991.

Den vollen Inhalt der Quelle finden

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Buchteile zum Thema "Amortized complexity"

1

Nipkow, Tobias. „Amortized Complexity Verified“. In Interactive Theorem Proving, 310–24. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-22102-1_21.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

2

Roland, Jérémie, und Mario Szegedy. „Amortized Communication Complexity of Distributions“. In Automata, Languages and Programming, 738–49. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02927-1_61.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

3

Fiedor, Tomáš, Lukáš Holík, Adam Rogalewicz, Moritz Sinn, Tomáš Vojnar und Florian Zuleger. „From Shapes to Amortized Complexity“. In Lecture Notes in Computer Science, 205–25. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-73721-8_10.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

4

Nikishkin, Vladimir. „Amortized Communication Complexity of an Equality Predicate“. In Computer Science – Theory and Applications, 212–23. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-38536-0_19.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

5

Cascudo, Ignacio, Ronald Cramer, Chaoping Xing und Chen Yuan. „Amortized Complexity of Information-Theoretically Secure MPC Revisited“. In Lecture Notes in Computer Science, 395–426. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-96878-0_14.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

6

Soisalon-Soininen, Eljas, und Peter Widmayer. „Amortized Complexity of Bulk Updates in AVL-Trees“. In Algorithm Theory — SWAT 2002, 439–48. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-45471-3_45.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

7

Cramer, Ronald, und Ivan Damgård. „On the Amortized Complexity of Zero-Knowledge Protocols“. In Advances in Cryptology - CRYPTO 2009, 177–91. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-03356-8_11.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

8

Golowich, Noah, und Madhu Sudan. „Round Complexity of Common Randomness Generation: The Amortized Setting“. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1076–95. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2020. http://dx.doi.org/10.1137/1.9781611975994.66.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

9

Cramer, Ronald, Ivan Damgård und Valerio Pastro. „On the Amortized Complexity of Zero Knowledge Protocols for Multiplicative Relations“. In Lecture Notes in Computer Science, 62–79. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-32284-6_4.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

10

Cramer, Ronald, Ivan Damgård, Chaoping Xing und Chen Yuan. „Amortized Complexity of Zero-Knowledge Proofs Revisited: Achieving Linear Soundness Slack“. In Lecture Notes in Computer Science, 479–500. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-56620-7_17.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Konferenzberichte zum Thema "Amortized complexity"

1

Baig, Mirza Ahad, Danny Hendler, Alessia Milani und Corentin Travers. „Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity“. In PODC '20: ACM Symposium on Principles of Distributed Computing. New York, NY, USA: ACM, 2020. http://dx.doi.org/10.1145/3382734.3406005.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

2

Ellen, Faith, Panagiota Fatourou, Joanna Helga und Eric Ruppert. „The amortized complexity of non-blocking binary search trees“. In the 2014 ACM symposium. New York, New York, USA: ACM Press, 2014. http://dx.doi.org/10.1145/2611462.2611486.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

3

Samorodnitsky, Alex, und Luca Trevisan. „A PCP characterization of NP with optimal amortized query complexity“. In the thirty-second annual ACM symposium. New York, New York, USA: ACM Press, 2000. http://dx.doi.org/10.1145/335305.335329.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

4

Giakkoupis, George, und Philipp Woelfel. „Randomized Mutual Exclusion with Constant Amortized RMR Complexity on the DSM“. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2014. http://dx.doi.org/10.1109/focs.2014.60.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

5

Chan, David Yu Cheng, und Philipp Woelfel. „Recoverable Mutual Exclusion with Constant Amortized RMR Complexity from Standard Primitives“. In PODC '20: ACM Symposium on Principles of Distributed Computing. New York, NY, USA: ACM, 2020. http://dx.doi.org/10.1145/3382734.3405736.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

6

Giakkoupis, George, und Philipp Woelfel. „Randomized Abortable Mutual Exclusion with Constant Amortized RMR Complexity on the CC Model“. In PODC '17: ACM Symposium on Principles of Distributed Computing. New York, NY, USA: ACM, 2017. http://dx.doi.org/10.1145/3087801.3087837.

Der volle Inhalt der Quelle

APA, Harvard, Vancouver, ISO und andere Zitierweisen

Wir bieten Rabatte auf alle Premium-Pläne für Autoren, deren Werke in thematische Literatursammlungen aufgenommen wurden. Kontaktieren Sie uns, um einen einzigartigen Promo-Code zu erhalten!