八岁儿童的大O? [英] Big-O for Eight Year Olds?

问题描述

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

I'm asking more about what this means to my code. I understand the concepts mathematically, I just have a hard time wrapping my head around what they mean conceptually. For example, if one were to perform an O(1) operation on a data structure, I understand that the number of operations it has to perform won't grow because there are more items. And an O(n) operation would mean that you would perform a set of operations on each element. Could somebody fill in the blanks here?

• 比如 O(n^2) 操作究竟会做什么?
• 如果操作的复杂度为 O(n log(n))，这到底意味着什么?
• 有人必须抽烟才能写出 O(x!) 吗?

推荐答案

一种思考方式是这样的:

One way of thinking about it is this:

O(N^2) 意味着对于每个元素，您正在对每个其他元素执行某些操作，例如比较它们.冒泡排序就是一个例子.

O(N^2) means for every element, you're doing something with every other element, such as comparing them. Bubble sort is an example of this.

O(N log N) 意味着对于每个元素，您正在做的事情只需要查看元素的 log N.这通常是因为您对可以让您做出有效选择的元素有所了解.最有效的排序就是一个例子，例如归并排序.

O(N log N) means for every element, you're doing something that only needs to look at log N of the elements. This is usually because you know something about the elements that let you make an efficient choice. Most efficient sorts are an example of this, such as merge sort.

O(N!) 意味着对 N 个元素的所有可能排列做一些事情.旅行商就是一个例子，这里有N！访问节点的方法，而暴力解决方案是查看每个可能排列的总成本，以找到最佳排列.

O(N!) means to do something for all possible permutations of the N elements. Traveling salesman is an example of this, where there are N! ways to visit the nodes, and the brute force solution is to look at the total cost of every possible permutation to find the optimal one.

这篇关于八岁儿童的大O?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！