一尘不染

大八岁的孩子?

algorithm

我想问更多关于这对我的代码意味着什么。我从数学上理解这些概念,我很难理解它们在概念上的含义。例如,如果要对数据结构执行O(1)操作,我知道它必须执行的操作数量不会增加,因为有更多的项。O(n)操作意味着您将对每个元素执行一组操作。有人可以在这里填补空白吗?

  • 就像O(n ^ 2)运算会做什么一样?
  • 如果操作是O(n log(n)),这意味着什么呢?
  • 有人要抽烟写O(x!)吗?

阅读 195

收藏
2020-07-28

共1个答案

一尘不染

一种思考方式是:

O(N ^ 2)意味着对于每个元素,您正在与其他每个元素一起做某事,例如比较它们。冒泡排序就是一个例子。

O(N log
N)意味着对于每个元素,您所做的事情仅需要查看元素的logN。这通常是因为您了解一些有关使您做出有效选择的要素的知识。最有效的排序就是这种示例,例如合并排序。

O(N!)意味着对N个元素的所有可能排列进行处理。一个旅行推销员就是一个例子,那里有N个!一种访问节点的方法,而强力解决方案是查看每种可能排列的总成本以找到最佳排列。

2020-07-28