stdcxx-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Anton Pevtsov (JIRA)" <j...@apache.org>
Subject [jira] Created: (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 Tue, 07 Feb 2006 10:00:00 GMT
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