这个 python 程序的大 O 表示法的时间复杂度是多少？

Question

我发现这个程序的时间复杂度很难计算，因为它涉及到很多内置方法。有人可以帮忙吗？基本上，问题是找到每个学科的最佳人选和 3 个整体表现最好的人！

from sys import argv
df=pd.read_csv(sys.argv[1])
subjects=['Maths','Biology','Physics','English','Chemistry','Hindi']
total=[]
for column in subjects:
  a=df[column].max()  #finding the maximum value in each column
  b=df.loc[(df[column]==a),['Name']] #locating the corresponding row of the found maximum value
print("Topper in "+column+" is "+re.sub("\[|\]|'","",str(b.values.tolist())))


df['total']=df['Maths']+df['Biology']+df['Physics']+df['Chemistry']+df['Hindi']+df['English']
df_v1=df.sort_values(by=['total'],ascending=False)
print("Best students in this class are: ")
for i in range(3):
 print(str(i+1)+"."+df_v1.iloc[i]['Name'])

输入的 csv 文件看起来像这样：

Name  Physics Chemistry Biology Maths Hindi English
Steve  99     1000      100     95    97    85
John    80     90        75     70    100   100

输出：

  Topper in maths is X
  Topper in physics is y
Overall best students are X,y,z

Answer 1

您的 for 循环遍历每行的所有列 => O(row * col) 复杂度。
总计的计算也是如此 => O(row * col)
sort_values 对一列中的所有值进行排序，通常，排序函数在理论上是 O(nLog(n))，所以这给我们 O(row * Log(row ))

总而言之，我们有 O(row * col) + O(row * col) + O(row * log(row) => O(row * col)

所以答案是 O(row * col)

编辑

如果 col << row，您实际上可能得到 O(rowlog(row))。所以如果列数是有限的，其实就是O(rowlog(row))

这个 python 程序的大 O 表示法的时间复杂度是多少？

What will the time complexity of this python program in Big O notation?

python

big-o

time-complexity

pandas