Блог пользователя C137

String length complexity...
Автор C137, история, 8 лет назад, По-английски

String str;

cin>>str;

for(int i=0;i<str.length();i++){

....

}

if str.length()=n, then the total complexity of the algorithm is n*n?? or just n?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Both string::size and string::length are synonyms and return the exact same value. Complexity : O(1).

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

Here is the C program to find length of string.

→ Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится -9 Проголосовать: не нравится

Most modern compilers do an optimization with the function call being repeated without any changes, so instead it memorizes the value returned by that function, but still can not rely on compiler to do that and it's better to do it manually as the following:

for(int i=0, length=str.length(); i<length; ++i){

// your code

}

the code above runs in O(n) complexity instead of O(n^2), and it would be remarkable that the code runs faster for large strings lengths.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    This is true for strlen() but not for string::length(), because the former is O(n) and the latter is O(1).

    → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    well i always store the length in a separate variable before the loop, but a friend told me that the complexity of length() is O(n) so i wanted to make sure about the information, thanks for the help :)

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The complexity for string::size()/length() is constant but of course it would be faster to store size in a variable (e.g. sz) because of:

      -Accessing (sz) is faster than accessing (string::size()/length())

      -Comparing int(i) to int(sz) is faster than comparing int(i) to unsigned int(string::size()/length())

      → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

read here http://www.cplusplus.com/reference/string/string/size/

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

.

→ Ответить