大O符号计算常量

Question

我已经创建了一个jaccard函数，其中我知道大O是O（n），我如何估计我的实现和计算机的常数？你知道吗

def jaccard(dict1,dict2):
   intersection={}
   for item in dict1.keys():
       if item in dict2.keys():
          intersection[item]=min(dict1[item],dict2[item])

   intersectiontot=maketotal(intersection)
   union = maketotal(dict1)+maketotal(dict2)-intersectiontot
   return intersectiontot/union

Answer 1

为了得到一个很好的常数估计值，你所能做的就是用大量不同大小的数据集进行大量的运行（试着保持系统的其余部分安静），将所有这些数据都绘制在散点图上，然后看看这些点是否适合接近一条直线的某个地方。你知道吗

这条线的斜率将给出常数因子。你知道吗

需要大范围的数据大小，以确保在执行时间中可以看到大小合理的更改。以相同的数据大小多次运行将有助于消除由系统上的其他事物引起的测量变化。你知道吗

我很惊讶你的特殊功能是O（n）-我会认为它是O（nm），其中n&m是你的两个字典的大小（除非一个字典总是比另一个小）。你知道吗

祝你好运。你知道吗

---

一个性能更高的解决方案（没有多个字典查找和重复的成员资格测试）可能是这样的：

 def jaccard(dict1,dict2):
     sentinel = object()
     intersection={}
     for key, value1 in dict1.items():
         value2 = dict2.get(key, sentinel)
         if value2 is not sentinel:
               intersection[item]=min(value1, value2)

     intersectiontot=maketotal(intersection)
     union = maketotal(dict1)+maketotal(dict2)-intersectiontot
     return intersectiontot/union

此函数在dict2中同时执行成员身份测试和查找，并且在找到密钥后不需要在dict1中进行单独的查找。你知道吗

根据maketotal所做的工作，可能会进一步改进这一点。你知道吗