Fast Algorithm for Computing the Upper Endpoint of Sample Variance for Interval Data: Case of Sufficiently Accurate Measurements |
| |
Authors: | Gang Xiang |
| |
Affiliation: | (1) Department of Computer Science, University of Texas at El Paso, 500 W. University, El Paso, TX 79968, USA |
| |
Abstract: | When we have n results x1,...,xn of repeated measurement of the same quantity, the traditional statistical approach usually starts with computing their sample
average E and their sample variance V. Often, due to the inevitable measurement uncertainty, we do not know the exact values of the quantities, we only know the
intervals xi of possible values of x1 In such situations, for different possible values xi∈ xi, we get different values of the variance. We must therefore find the range V of possible values of V. It is known that in general, this problem is NP-hard. For the case when the measurements are sufficiently accurate (in some
precise sense), it is known that we can compute the interval V in quadratic time O(n2). In this paper, we describe a new algorithm for computing V that requires time O(n log(n)) (which is much faster than O(n2)). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|