Sri*_*aju 9 string algorithm math complexity-theory string-conversion
将字符串转换为等效数字的复杂性是什么,反之亦然？它是否会根据编程语言而改变？
从表面上看,需要遍历整个字符串以将其转换为数字,因此它是O(n),还是使用了一些类型转换？
当我写一个程序检查一个给定的数字是否是回文时,就会出现这种疑问.一种方法是将数字除以基数(此处为10),累加数字,并将它们放在一起.示例:309/10 = rem(9),30/10 = rem(0),3/10 = rem(3).我们得到903.
我采用的另一种方法是将这个数字转换成一个字符串,因为字符串有大量的成员函数来分割,反转等,所以代码更短更清晰,但这是最好的方法吗？
Cha*_*via 14
数字字符串是以位置表示法格式化的数字 - 因此需要考虑每个数字的值乘以基数的幂,以便将数字转换为二进制格式.
所以是的,这是一个O(N)操作,因为随着更多数字的添加,运行时间会线性增加.但是,在实践中,N可能受到语言支持的任何数值数据类型的限制(例如int32_t,int64_t).但是如果使用任意精度数字类型(某些语言,如Python,默认使用)那么数字的数量没有限制(显然除了可用内存).