计数比较用于算法分析

Question

假设我正在分析一个算法，我想计算比较次数。

假设这样的结构：

if (a == b){
  ...
}
else if (a == c) {
  ...
}
else if (a == d) {
  ...
}
else {
  ...
}

计算比较的最佳方法是什么？

我认为这是要走的路：

int compare = 0
compares++; //will always do the first compare
if (a == b){
  ...
}
else if (a == c) {
  compares++; //add another because we got here
  ...
}
else if (a == d) {
  compares += 2; //add 2 because of this one and the previous else if
  ...
}
else {
  compares += 3; //etc
  ...
}

这是对的吗？

Answer 1

是的，这是正确的，但是您可以使用逗号运算符更简洁，更健壮地编写它（假设这是C/C++/JS）：

if (compares++, a == b){
  ...
}
else if (compares++, a == c) {
  ...
}
else if (compares++, a == d) {
  ...
}
else {
  ...
}

此外，如果您使用的是C++（或任何具有运算符重载的语言），则可以使用自定义对象并覆盖比较运算符并将其计数。这样，您只需更改变量的类型，而无需更改代码的其余部分。

Answer 2

如果你正在分析一般的算法，你应该使用Big O并假设最坏的情况。您正在尝试查看集合中的一个值是否等于另一个值。在最坏的情况下，您必须进行 n-1-1 比较，以便算法线性增长，其中 n 是集合中的值数。因此，您可以将算法分类为 O（n）。

如果要进行定量比较，请确保在每个算法中以相同的顺序比较值，因为这会改变结果。那么如果a等于多个值呢？