What is the complexity of str() function in Python3?-CodePudding

I have to create a function respecting an O(n) complexity and to do that i want to use the str() function.

Can someone explain me if :

str(1000)

Is this code O(1) or O(4) because of the 1 0 0 0 ?

CodePudding user response：

O(n) in the context of a data structure just means if there are n items then an operation on that structure will require (in the order of) n iterations or passes to achieve the desired result. If you're constructing a string from an integer, then I guess the complexity would be O(log10(n))

EDIT: from the Python docs:

If neither encoding nor errors is given, str(object) returns object.str(), which is the “informal” or nicely printable string representation of object.

Python detects that the object is an int, therefore it will create a string from that int. One way of implementing this conversion is:

if n == 0:
    return "0"
negative = n < 0
if negative:
    n = -n
out = ""
while n > 0:
    digit = n % 10
    n /= 10
    out = chr(48   digit)   out
if negative:
    out = "-"   out

The number of iterations inside that while loop depends on the number of digits in decimal that n contains, which is log10(n).

CodePudding user response：

The function is used for string conversion. That means converting each of the value into a string. The complexity is depended on the length. If the the full length is n so the complexity will be O(n). If the size is a fixed number, in this case it will be executed a constant size. We represent the constant as O(1).