E23563: 多项式时间复杂度

string, implementation, http://cs101.openjudge.cn/practice/23563

在计算机科学中，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （满足 n > n0，n0为常数）的输入，它至多需要 6n^2+5n^3的时间运行完毕，那么它的渐近时间复杂度是 O(n^3)。

输入

一行，一个字符串表示此算法的整体运算次数，保证每项形如 x^b 或 ax^b，其中a、b均为非负整数；保证项与项之间以+号连接，保证至少存在一项。保证a, b <= 10^8

输出

一行，一个字符串 n^k 表示此算法的渐进时间复杂度为 O(n^k). 若此算法的渐进时间复杂度为 O(1)，请输出 n^0

样例输入

Sample Input1:
6n^2+5n^3  

Sample Output1:
n^3

样例输出

Sample Input2:
99n^10+n^9+0n^100

Sample Output2:
n^10

来源：2021fall-cs101, lyh

思路：本题核心在于一个坑，就是有可能某个较大质数的系数是0，但是这个坑在样例中体现了，那就比较好避免了。注意对比的时候变量的类型，之前的各种切分都是字符串，需要变成整型。

python

poly=input().split('+')
ans=0
for ch in poly:
    coe,exp=ch.split('n^')
    if coe!='0' and int(exp)>ans:
        ans=int(exp)
print(f'n^{ans}')

字符串实现

python

ps = input().split('+') 
ns = [(i.split('n^')) for i in ps] 
result = 0 
for i in ns: 
    if int(i[1]) > result and i[0] != '0': 
        result = int(i[1]) 
print('n^{}'.format(result))

字符串实现加排序

python

s = input().split('+')
l = []
for x in s:
    if x[0] == 'n':
        x = '1' + x
    l.append(list(map(int, x.split('n^'))))
l.sort(key=lambda x: -x[1])
for x in l:
    if x[0] != 0:
        print(f'n^{x[1]}')
        break

正则表达式实现

python

# 2022fall-cs101, 楼翔
import re
intermedia = input()
listy = [int(x) for x in re.findall(r".(?<!\+0)n\^(\d+)", intermedia)] + [0]
print("n^" + str(max(listy)))

思路：也是正则表达式提取幂，不过很坑的一点是前面可能有0的系数需要排除，因此错了一次。因此正则表达式先匹配一个非0系数[1-9]\d*，再使用"()"捕获组捕获后面的幂。

python

import re 

st = input()

def findpower(st):
    pattern = r"[1-9]\d*n\^(\d*)"
    match = re.findall(pattern, st)
    if not match:
        print("n^0")
        return
    match = list(map(int,match))
    pow = max(match)
    print("n^"+str(pow))
    return

findpower(st)

思路：正则匹配系数和指数

python

import re
def time_complexity(s):
    pattern = r'(\d+)?n\^(\d+)'
    result_list = re.findall(pattern, s)
    result_exp = []
    for i, exp in result_list:
        if i != '0':
            result_exp.append(int(exp))
    return f'n^{max(result_exp)}'

print(time_complexity(input()))

python

s = input().split('+')
res = 0
for i in s:
        pos = i.find('^')
        if pos == -1:
                continue

        if pos!=1 and int(i[:pos-1]) == 0:
                continue

        res = max(res, int(i[pos+1:]))

print(f"n^{res}")

python

a=input().split(sep='+')
hh=[]
for i in a:
    if i[0]!='0':
        k=i.find(('n'))
        h=int(i[k+2:])
        hh.append(h)
print(f'n^{max(hh)}')

E23563: 多项式时间复杂度 ​

E23563: 多项式时间复杂度