如何知道什么时候大O是对数？ [英] How to know when Big O is Logarithmic?

问题描述

我的问题是从后大O的纯英文解释。我不知道对数的复杂性的确切含义。我知道我可以让与的时间之间的回归操作的数量，并计算在X平方值，并确定这样的复杂性。不过，我想知道一个方法来快速确定在纸上。

My question arises from the post "Plain English Explanation of Big O". I don't know the exact meaning for logarithmic complexity. I know that I can make a regression between the time and the number of operations and calculate the X-squared value, and determine so the complexity. However, I want to know a method to determine it quickly on paper.

你如何确定对数的复杂性？是否有一些好的标准？

How do you determine logarithmic complexity? Are there some good benchmarks?

推荐答案

不知道这是什么意思，但是......当你正在使用像$ P $垫出的数据结构，对数的复杂性通常出现平衡二叉树，其中包含1个节点在根，2个孩子，4个孙子孙女，8个曾孙等，基本上在每个级别的节点数量被乘以某个系数（2），但仍然只有一个那些参与在迭代。或者作为另一个例子，一个循环，其中指数加倍在各步骤：

Not sure if this is what you mean, but... logarithmic complexity usually arises when you're working with a spread-out data structure like a balanced binary tree, which contains 1 node at the root, 2 children, 4 grandchildren, 8 great-grandchildren, etc. Basically at each level the number of nodes gets multiplied by some factor (2) but still only one of those is involved in the iteration. Or as another example, a loop in which the index doubles at each step:

for (int i = 1; i < N; i *= 2) { ... }

这样的事情是对数的复杂性的特征。

Things like that are the signatures of logarithmic complexity.

这篇关于如何知道什么时候大O是对数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！