最小総和法に対する2つの O (n log n)アルゴリズム

概要

論文の詳細を見る
As a method for floating point summation which reduces truncation errors, in this paper, a new technique, minimal summation, is presented. This technique sums up floating point numbers from small to large. An ordinary algorithm for this problem takes O(n^2) run time where n is the size of data, while two algorithms presented take both O(n log n) run time. One applies so-called Heapsort method, the other utilizes the data structure of queues. Finally it is shown that the inherent complexity of this problem is also O(n log n).
一般社団法人情報処理学会の論文
1977-09-15