关于Python的一个小程序及时间复杂度

img


写出两种方法加以注释并分析时间复杂度

def b4to10(x,conte=0):
        if x>10:
            return x%10*4**conte+b4to10(x//10,conte+1) #O(1)
        return x*4**conte #O(1)


if __name__ == '__main__':
    #思路,将四进制数转换为10进制数后判断是否是5的倍数
    # 时间复杂度分析 转换4进制函数为递归函数,时间复杂度为O(n)
    # 语句执行一次为O(1)
    # 语句执行一个循环为O(n)
    # 语句执行一个双循环为O(n**m)
    # 下面我将时间复杂度注释在语句后面
    import time

    b4 = int(input('输入4进制的数：'))# O(1)
    start = time.time()#O(1)
    b10number=b4to10(b4)#O(N)
    if b10number%5==0:#O(1)
        print(f"{b4}是5的倍数")#O(1)
    else:
        print(f"{b4}不是5的倍数")#O(1)
    end = time.time()#O(1)
    print(end-start)#O(1)
    # 中上 时间复杂度为 O(6)+O(n)

img


import time
n = input('输入4进制的数：')
s = time.time()
a = int(n, base=4)
print(f'{n}是10进制数:{a}')
if a % 5 == 0:
    print(f'{n}是5的倍数')
else:
    print(f'{n}不是5的倍数')
print(f'用时：{time.time()-s}秒')

img