Mercurial > hg > octave-max
changeset 9923:31d644253380
document lookup complexity
| author | Jaroslav Hajek <highegg@gmail.com> |
|---|---|
| date | Sat, 05 Dec 2009 21:45:45 +0100 |
| parents | 3a8327d51ed4 |
| children | d0d6ff39db54 |
| files | src/ChangeLog src/DLD-FUNCTIONS/lookup.cc |
| diffstat | 2 files changed, 7 insertions(+), 4 deletions(-) [+] |
line wrap: on
line diff
--- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,3 +1,7 @@ +2009-12-05 Jaroslav Hajek <highegg@gmail.com> + + * DLD-FUNCTIONS/lookup.cc (Flookup): Document complexity. + 2009-12-05 Jaroslav Hajek <highegg@gmail.com> * DLD-FUNCTIONS/lookup.cc (do_numeric_lookup): Rewrite.
--- a/src/DLD-FUNCTIONS/lookup.cc +++ b/src/DLD-FUNCTIONS/lookup.cc @@ -187,10 +187,9 @@ The result is undefined if @var{table} is not monotonic, or if\n\ @var{table} contains a NaN.\n\ \n\ -The algorithm used by lookup is standard binary search, with optimizations\n\ -to speed up the case of arrays containing pre-ordered portions (sampling).\n\ -In particular, looking up a single entry is of logarithmic complexity\n\ -(unless a conversion occurs due to non-numeric or unequal types).\n\ +The complexity of the lookup is O(M*log(N)) where N is the size of @var{table}\n\ +and M is the size of @var{y}. In the special case when @var{y} is also sorted,\n\ +the complexity is O(min(M*log(N),M+N)).\n\ \n\ @var{table} and @var{y} can also be cell arrays of strings\n\ (or @var{y} can be a single string). In this case, string lookup\n\