学习python3的野路子——关于时间复杂度

关于时间复杂度：最直观的理解是，运行的快慢。可以参照相对严谨而又好懂的资料^[1]。说完了这些，我们看看题目。
本题通过生成至位数字并对这些数字一次求和，会面临运行超时的情况。猜测原因是因为数字长度过长，在做加法时，进位处理需要花费较长的时间。因此改变求和策略，如下：

    1
   11
  111
+1111
-------

列出上述表达式，依次从低位往高位做带进位的加法。
每次加法可以表示为(其中的表示从低位开始的第位，最低位为)，取出个位作为中第为的值，将其余部分当做进位。

# PAT中的基础编程题目集函数题7-38

# 超时版本
# A, N = input().split()
# A = int(A); N = int(N)
# sum = 0
# item = A
# while N:
#     N -= 1
#     sum += item
#     item = item * 10 + A
# print(sum)

A, N = input().split()
A = int(A); N = int(N)
sum = ''
c = 0
while N:
    tmp = A * N + c
    sum += str(tmp % 10) # 取个位情况
    c = tmp // 10 # 进位
    N -= 1
if sum == '':
    print(0) # 零的情况
elif c:
    print(str(c) + sum[: : -1]) # 考虑进位
else :
    print(sum[: : -1]) # 最后进位为0

参考

---

1. https://www.jianshu.com/p/f4cca5ce055a ↩