Sinopsis
Excerpt from Amortized Complexity of Data Structures, Vol. 255
Introduction Single-level Hashing Model Uniform Hash Functions and Worst-case Complexity Nonuniform Hash Functions Amortization Multilevel Hashing Model Partial Hashing Model Adversary Two Random Sampling Lemmas The Worst-case Lower Bound Amortization.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.
"Sinopsis" puede pertenecer a otra edición de este libro.
Reseña del editor
Excerpt from Amortized Complexity of Data Structures, Vol. 255
Introduction Single-level Hashing Model Uniform Hash Functions and Worst-case Complexity Nonuniform Hash Functions Amortization Multilevel Hashing Model Partial Hashing Model Adversary Two Random Sampling Lemmas The Worst-case Lower Bound Amortization.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.
Reseña del editor
Excerpt from Amortized Complexity of Data Structures, Vol. 255
This thesis investigates the amortized complexity of some fundamental data structure problems and introduces interesting ideas for proving lower bounds on amortized complexity and for performing amortized analysis. The problems are as follows:
Dictionary Problem: A dictionary is a dynamic set that supports searches of elements and changes under insertions and deletions of elements. It is open whether there exists a dictionary data structure that takes constant amortized time per operation and uses space polynomial in the dictionary size. We prove that dictionary operations require log-logarithmic amortized time under a multilevel hashing model that is based on Yao's cell probe model.
Splay Algorithm's Analysis: Splay is a simple, efficient algorithm for searching binary search trees, devised by Sleator and Tarjan, that uses rotations to reorganize the tree. Tarjan conjectured that Splay takes linear time to process deque operation sequences on a binary tree and proved a special case of this conjecture called the Scanning Theorem. We prove tight bounds on the maximum numbers of various types of right rotations in a sequence of right rotations performed on a binary tree. One of the lower bounds refutes a conjecture of Sleator. We apply the upper bounds to obtain a nearly linear upper bound for Tarjan's conjecture. We give two new proofs of the Scanning Theorem, one of which is a potential-based proof that solves a problem of Tarjan.
Set Equality Problem: The task of maintaining a dynamic collection of sets under various operations arises in many applications. We devise a fast data structure for maintaining sets under equality-tests and under creations of new sets through insertions and deletions of elements. Equality-tests require constant time and set-creations require logarithmic amortized time. This improves previous solutions.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.
"Sobre este título" puede pertenecer a otra edición de este libro.
Otras ediciones populares con el mismo título
Resultados de la búsqueda para Amortized Complexity of Data Structures, Vol. 255 (Classic...
Imagen del vendedor
Amortized Complexity of Data Structures, Vol. 255 (Classic Reprint)
Impresión bajo demandaLibrería: Forgotten Books, London, Reino Unido
Calificación del vendedor: 4 de 5 estrellas
Paperback. Condición: New. Print on Demand. This book delves into the topic of amortized complexity, a valuable framework for analyzing the performance of data structures. The author explores fundamental data structure problems, such as the Dictionary Problem, Splay Algorithms, and Set Equality Problem. Through a series of intricate and engaging examples, the author demonstrates the power of amortized analysis, enabling readers to make insightful estimations on the behavior of data structures under various usage patterns. The book contributes to the ongoing conversation on data structure complexity and provides fresh perspectives on devising and evaluating efficient data structures. This book is a reproduction of an important historical work, digitally reconstructed using state-of-the-art technology to preserve the original format. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in the book. print-on-demand item. Nº de ref. del artículo: 9781332099085_0
Comprar nuevo
EUR 16,26
Gastos de envío gratis
Se envía de Reino Unido a Estados Unidos de America
Se envía de Reino Unido a Estados Unidos de America
Cantidad disponible: Más de 20 disponibles
Imagen de archivo
Amortized Complexity of Data Structures, Vol 255 Classic Reprint
Librería: PBShop.store US, Wood Dale, IL, Estados Unidos de America
Calificación del vendedor: 5 de 5 estrellas
PAP. Condición: New. New Book. Shipped from UK. Established seller since 2000. Nº de ref. del artículo: LW-9781332099085
Comprar nuevo
EUR 22,82
Gastos de envío gratis
Se envía dentro de Estados Unidos de America
Se envía dentro de Estados Unidos de America
Cantidad disponible: 15 disponibles
Imagen de archivo
Amortized Complexity of Data Structures, Vol 255 Classic Reprint
Librería: PBShop.store UK, Fairford, GLOS, Reino Unido
Calificación del vendedor: 4 de 5 estrellas
PAP. Condición: New. New Book. Shipped from UK. Established seller since 2000. Nº de ref. del artículo: LW-9781332099085
Comprar nuevo
EUR 21,30
Envío por EUR 3,77
Se envía de Reino Unido a Estados Unidos de America
Se envía de Reino Unido a Estados Unidos de America
Cantidad disponible: 15 disponibles