这种复杂度大概稳定能得多少分
查看原帖
这种复杂度大概稳定能得多少分
414224
zxyluogu楼主2021/10/28 10:05

我主要不清楚我的代码中

while(a[f][i].a>q.top()&&q.size()) q.pop();

平均执行多少次,根据数据的强弱有可能 O(logmi)O(\log m_{i})O(mi)O(m_{i})  (最弱O(1))

m=m1+m2m=m_1+m_2
那么我的代码可能O(nmlog2m)O(nm\log^2 m) (常数大约14\frac1 4)或 O(nmmlogm)O(nm\sqrt m\log m) ,最差可能O(nm2logm)O(nm^2\log m)(常数大约 18\frac1 8

如果简单地按 5000×5000×log225000÷45000\times5000\times\log_2^2 5000\div4 算,结果约等于 9.4×1089.4\times10^8,应该能40分
如果简单地按 5000×50002×log25000÷85000\times5000^2\times\log_2 5000\div8 算,结果大于 101010^{10},只能得20分

2021/10/28 10:05
加载中...