Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Stable in situ sorting and minimum data movement (1990)
    Springer
    BIT 30 (1990), S. 220-234 
    Details
    ISSN: 1572-9125
    Keywords: E.5 ; F.2.2
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper, we describe an algorithm to stably sort an array ofn elements using only a linear number of data movements and constant extra space, albeit in quadratic time. It was not known previously whether such an algorithm existed. When the input contains only a constant number of distinct values, we present a sequence ofin situ stable sorting algorithms makingO(n lg(k+1) n+kn) comparisons (lg(K) means lg iteratedk times and lg* the number of times the logarithm must be taken to give a result ≤ 0) andO(kn) data movements for any fixed valuek, culminating in one that makesO(n lg*n) comparisons and data movements. Stable versions of quicksort follow from these algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02017344
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Analysis of the standard deletion algorithms in exact fit domain binary search trees (1990)
    Springer
    Algorithmica 5 (1990), S. 295-311 
    Details
    ISSN: 1432-0541
    Keywords: Binary search tree ; Data structure ; Average case analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract It is well known that the expected search time in anN node binary search tree generated by a random sequence of insertions isO(logN). Little has been published about the asymptotic cost when insertions and deletions are made following the usual algorithms with no attempt to retain balance. We show that after a sufficient number of updates, each consisting of choosing an element at random, removing it, and reinserting the same value, that the average search cost is Θ(N 1/2).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840390
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Optimum reorganization points for arbitrary database costs (1982)
    Springer
    Acta informatica 18 (1982), S. 17-30 
    Details
    ISSN: 1432-0525
    Keywords: D.4.3 ; F.2.2 ; G.2.1 ; H.2.2
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary The performance deterioration caused by updates to databases or data structures can be overcome by reorganizing the structure from time to time. In previous work, optimal reorganization intervals were determined for linearly increasing deterioration costs and linearly growing reorganization cost. To date only heuristics have been available for non-linear costs, and no work has been published on optimal solutions. This paper extends previous results by identifying the reorganization points problem as a shortest route problem and by providing a dynamic programming algorithm to find optimal reorganization points when reorganization and deterioration costs are arbitrary. It is shown that our method usesθ(T **2) basic operations andθ(T) space, whereT represents the database lifetime. Furthermore, we note that no algorithm can solve this problem in significantly less time or space. Examples involving linear and non-linear costs are presented and discussed. Finally, the algorithm is modified to find the optimal sequence of reorganizations to be applied in situations where partial reorganizations are possible.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00625278
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...