The analyses of many algorithms and data structures (such as digital search trees) for searching and sorting are based on the representation of the keys involved as bit strings and so count the number of bit compariso...
详细信息
The analyses of many algorithms and data structures (such as digital search trees) for searching and sorting are based on the representation of the keys involved as bit strings and so count the number of bit comparisons. On the other hand, the standard analyses of many other algorithms (such as Quicksort) are performed in terms of the number of key comparisons. We introduce the prospect of a fair comparison between algorithms of the two types by providing an average-caseanalysis of the number of bit comparisons required by Quicksort. Counting bit comparisons rather than key comparisons introduces an extra logarithmic factor to the asymptotic average total. We also provide a new algorithm, "BitsQuick", that reduces this factor to constant order by eliminating needless bit comparisons.
Skylines emerged as a useful notion in database queries for selecting representative groups in multivariate data samples for further decision making, multiobjective optimization, or data processing, and the k-dominant...
详细信息
Skylines emerged as a useful notion in database queries for selecting representative groups in multivariate data samples for further decision making, multiobjective optimization, or data processing, and the k-dominant skylines were naturally introduced to resolve the abundance of skylines when the dimensionality grows or when the coordinates are negatively correlated. We prove in this paper that the expected number of k-dominant skylines is asymptotically zero for large samples when 1 <= k <= d - 1 under two reasonable (continuous) probability assumptions of the input points, d being the (finite) dimensionality, in contrast to the asymptotic unboundedness when k = d. In addition to such an asymptotic zero-infinity property, we also establish a sharp threshold phenomenon for the expected (d - 1)-dominant skylines when the dimensionality is allowed to grow with n, the sample size. Several related issues, such as the dominant cycle structures, the numerical aspects, and the practical implications, are also briefly studied.
We analyse the running time of Treapsort, a sorting algorithm in the MOQA(1) programming language, which acts on treaps. We show that, using the 'partial permutation' model of Banderier et al. (2003) [1], Trea...
详细信息
We analyse the running time of Treapsort, a sorting algorithm in the MOQA(1) programming language, which acts on treaps. We show that, using the 'partial permutation' model of Banderier et al. (2003) [1], Treapsort has smoothed complexity Theta (sigma(-1)n ln n) for treaps of size n. We also show that the multiset of running times of Treapsort on all treaps of size n is equal to the multiset of running times of Quicksort on all lists of length n. (C) 2013 Elsevier B.V. All rights reserved.
We consider the gap between the cost of an optimal assignment in a complete bipartite graph with random edge weights, and the cost of an optimal traveling salesman tour in a complete directed graph with the same edge ...
详细信息
We consider the gap between the cost of an optimal assignment in a complete bipartite graph with random edge weights, and the cost of an optimal traveling salesman tour in a complete directed graph with the same edge weights. Using an improved "patching" heuristic, we show that with high probability the gap is O((ln n)(2)/n), and that its expectation is Omega(1/n). One of the underpinnings of this result is that the largest edge weight in an optimal assignment has expectation Theta(ln n/n). A consequence of the small assignment-TSP gap is an e((O) over tilde(root n))-time algorithm which, with high probability, exactly solves a random asymmetric traveling salesman instance. In addition to the assignment-TSP gap, we also consider the expected gap between the optimal and second-best assignments;it is at least Omega(1/n(2)) and at most O(ln n/n(2)).
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas (Li and Vitanyi, An Introduction to Kolmogorov Complexity and its Applications, Springer, New Yor...
详细信息
The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas (Li and Vitanyi, An Introduction to Kolmogorov Complexity and its Applications, Springer, New York, 1997). To further demonstrate its power and elegance we exhibit new simple proofs using the incompressibility method. (C) 2000 Elsevier Science B.V. All rights reserved.
We solve the open problem of characterizing the leading constant in the asymptotic approximation to the expected cost used for random partial match queries in random k-d trees. Our approach is new and of some generali...
详细信息
We solve the open problem of characterizing the leading constant in the asymptotic approximation to the expected cost used for random partial match queries in random k-d trees. Our approach is new and of some generality;in particular, it is applicable to many problems involving differential equations ( or difference equations) with polynomial coefficients.
The convex hull of n points drawn independently from a uniform distribution on the interior of a d-dimensional polytope is investigated. It is shown that the expected number of vertices is O(logd–1n) for any polytope...
详细信息
The convex hull of n points drawn independently from a uniform distribution on the interior of a d-dimensional polytope is investigated. It is shown that the expected number of vertices is O(logd–1n) for any polytope, the expected number of vertices is Ω(logd–1n) for any simple polytope, and the expected number of facets is O(logd–1n) for any simple polytope. An algorithm is presented for constructing the convex hull of such sets of points in linear average time.
暂无评论