python中类型转换函数的时间复杂度是多少？

Question

例如， int(x) float(x) str(x) 它们的时间复杂度是多少？

Answer 1

对此没有明确的答案，因为它不仅取决于您要转换成的类型，还取决于您要转换的类型。

\n

让我们只考虑数字和字符串。int为了避免到处写“log”，我们通过说 n 是表示它需要多少位或数字来测量 an 的大小。（渐近地，计算位或数字并不重要。）对于字符串，显然我们应该让 n 为字符串的长度。没有任何有意义的方法来衡量“输入大小”float，因为浮点数都占用相同的空间量。

\n

\n
• 转换int,float或str转换为其自己的类型应该需要 \xce\x98(1) 时间，因为它们是不可变的对象，因此甚至不需要进行复制。
\n
• 将 an 转换int为 afloat应该需要 \xce\x98(1) 时间，因为您最多只需要从int来查找尾数，并读取位长度来查找指数。
\n
• 将 an 转换int为 astr应该采用 \xce\x98(n ² ) 时间，因为您必须执行 \xce\x98(n) 除法和余数运算才能找到 n 个数字，并且每个算术运算都需要 \xce\x98(n)时间，因为涉及的整数的大小。
\n
• 将 a 转换str为 oughtint需要 \xce\x98(n ² ) 时间，因为您需要对大小为 \xce\x98(n) 的整数进行 \xce\x98(n) 乘法和加法。
\n
• 将 a 转换str为 afloat应该需要 \xce\x98(n) 时间。该算法只需要从字符串中读取固定数量的字符进行转换，每个字符的浮点算术运算（或对有界int值的运算以避免中间舍入错误）需要 \xce\x98(1) 时间；但无论如何，算法都需要查看其余字符，以便在ValueError格式错误时引发错误。
\n
• 将 a 转换float为任何类型需要 \xce\x98(1) 时间，因为只有有限多个不同的float值。
\n

\n

我说“应该”是因为我还没有检查实际的源代码；这是基于转换算法需要做什么，以及实际使用的算法并不渐近地比它们需要的更糟糕的假设。

\n

当基数是 2 的幂（例如或）时，可能存在特殊情况来优化str- 到 -转换，因为这可以在不进行算术的情况下完成。如果这些情况被优化，那么它们应该花费 \xce\x98(n) 时间而不是 \xce\x98(n ² )。同样，将 an 转换为以 2 的幂为基数的 a（例如使用 or函数）应该花费 \xce\x98(n) 时间。intint('11001010', 2)int('AC5F', 16)intstrbinhex

\n