1

so what I need is a bit hard to describe for me, so I start with giving a context: I have a list of numbers that is not sorted (yet). One part of a more complex algorithm is that I need a rough approximation of a list of arbitrary numbers so that I can throw a number into that approximation and it returns a likely position in the list (after I sorted the list).

What I am doing right now is to get the smallest and biggest number in the list and just create a straight line through them and use this as my approximation. This way I can "sort in" all the other numbers on the line. As I already mentioned, a rough approximation is sufficient, that is why I need it in linear time (a full sort would require O(n). My approach with the straight line already delivers acceptable results, but the better my approximation the faster the whole algorithm will run, so my question is: Can I somehow get a more accurate approximation in linear time?

Tia
  • 111
  • 3

1 Answers1

1

What you're doing is selecting the elements at indices (in the sorted list) $0$ and $n$ and performing a linear fit between them in order to approximate your list. A generalization of this is to select the elements at indices $0, \lfloor n/k\rfloor, \lfloor 2n/k\rfloor,\ldots,n$ for some $k\geq 1$, and then perform a piecewise linear fit between them. For any fixed $k$ there is a randomized algorithm for this which runs in expected linear time, although the constant factor will grow with $k$. There's probably a deterministic linear time algorithm as well, but I only know of one for $k=1,2$ and even when $k=2$ the algorithm is complicated and has a large constant factor. The algorithm just comes from a simple algorithm for finding the element of index $i$ in a list $A$ (after sorting) for any $i$.

$\mathrm{FIND}(A,i)$:

  1. Choose a random $x\in A$.
  2. Partition $A\setminus \{x\}$ into $A_1$ and $A_2$ such that $A_1=\{y\in A:y<x\}$ and $A_2=\{y\in A:y>x\}$.
  3. If $|A_1|=i$ return $x$.
  4. If $|A_1|<i$ return $\mathrm{FIND}(A_2, i - |A_1|-1)$.
  5. If $|A_1|>i$ return $\mathrm{FIND}(A_1, i)$.

In order to find the elements of indices $0, \lfloor n/k\rfloor, \lfloor 2n/k\rfloor,\ldots,n$ all you have to do is run $\mathrm{FIND}$ $k+1$ times. Drawing a straight line from the $0$th element to the $\lfloor n/k\rfloor$st, the $\lfloor n/k\rfloor$st to $\lfloor 2n/k\rfloor$st, etc. gives you the desired approximation.

Alex Becker
  • 60,569
  • Thank you Alex, I have two questions about this, as I am not a native speaker and I do not have a good mathematical background: What does "expected linear time" mean? That in the worst case it runs slower but I can still expect it to run in linear time most of the times? Then can you recommend some literature on this so I can get into it more? – Tia Mar 27 '13 at 16:48
  • @Tim "Expected linear time" means that the expected value of the runtime is linear. It's a more precise way of saying that on average the algorithm runs in linear time. If you really want to learn about algorithms, I'd recommend the book "Algorithm Design" by Kleinberg and Tardos. The algorithm I gave is very similar to one which appears in chapter 13, I believe. – Alex Becker Mar 27 '13 at 17:15
  • If I understand this I have expected linear time for a single element of my list. What I want is something that has linear time for my whole list. Am I misunderstanding this? – Tia Apr 01 '13 at 13:15
  • @Tim You have expected linear time for each element you find. If you find a fixed number of elements, this gives you expected linear time for the approximation of your list. There is no expected linear time algorithm for sorting a list. – Alex Becker Apr 01 '13 at 13:59