incubator-stdcxx-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Martin Sebor (JIRA)" <j...@apache.org>
Subject [jira] Commented: (STDCXX-138) Complexity tests are not strict enough for some algorithms when the expected complexity is a function of the given sequence length (not exact count)
Date Wed, 08 Feb 2006 01:59:59 GMT
    [ http://issues.apache.org/jira/browse/STDCXX-138?page=comments#action_12365508 ] 

Martin Sebor commented on STDCXX-138:
-------------------------------------

See this thread for background:
http://mail-archives.apache.org/mod_mbox/incubator-stdcxx-dev/200602.mbox/%3c43E80945.4060503@roguewave.com%3e

> Complexity tests are not strict enough for some algorithms when the expected complexity
is a function of the given sequence length (not exact count)
> ----------------------------------------------------------------------------------------------------------------------------------------------------
>
>          Key: STDCXX-138
>          URL: http://issues.apache.org/jira/browse/STDCXX-138
>      Project: C++ Standard Library
>         Type: Improvement
>   Components: 25. Algorithms
>     Versions: 4.1.3
>  Environment: all
>     Reporter: Anton Pevtsov
>     Priority: Minor
>      Fix For: 4.1.4

>
> Affects tests for sort, stable_sort, partial_sort, partial_sort_copy, nth_element, etc
algorithms where the complexity is O(f(N)), where N is the length of the test sequence, f(N)
- some function of N: log N, N log N, N. 
> It is necessary to investigate each algorithm to find the worst case for it and use the
complexity on this worst sequence as the upper bound in tests. Currently "magic" coefficients
are used.

-- 
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
   http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
   http://www.atlassian.com/software/jira


Mime
View raw message