Efficient method for identifying few largest differences from a list of numbers
US7653673B1 · kind B1 · utility
0Cited by
2References
1Claims
0Family size
Assignee
Inventors
Key dates
| Filing date | Jul 19, 2005 |
| Grant date | Jan 26, 2010 |
| Priority date | — |
| Expiry date | Oct 12, 2027 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/026
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method is provided that finds the largest ‘k’ difference values in decreasing order from a list of ‘n’ arbitrary numbers. The method uses the property of sorted numbers to organize the list of all the differences in a way that reduces the size of the solution space. The time complexity of the solution space using the method is O(k2), as compared to O(n2) in the conventional exhaustive method. The overall time complexity of the method is bound by the complexity of the algorithm used to sort the input list of numbers. The memory complexity of the method is less than the exhaustive method when k<<n.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.