complexity-theory - 什么是汉明距离中的大 O？

Question

我已经在 MATLAB 中实现了类似于汉明距离的代码。对于输入，我有一个 matix。我想应用我的使用汉明距离的公式。我的公式是这样的：

方式是考虑两行（x，y）并应用公式。|xy| 是汉明距离两排。然后获得这些行的最大项目项。喜欢

x=(1,0.3 , 0 )
y=(0 , 0.1, 1)

对于矩阵的每两行获得 S，cod 在 matlab 中：

for j=1:4
 x=fin(j,:)
for i=j+1:5
 y=fin(i,:)

 s1= 1-hamming1
 end
 end

我的问题是：我的代码和公式中的复杂性或 big-o 是什么？什么是复杂性汉明距离？

Answer 1

x该算法在和y- -的长度的乘积中是线性的，O(len(x)*len(y))如双和所示。

但是请注意，由于您的问题中有很多错别字以及代码中的硬编码常量（从技术上讲，这使得算法复杂性保持不变），因此很难绝对确定。