我正在学习大O符号的运行时间和摊销时间。我理解O（n）线性时间的概念，这意味着输入的大小成比例地影响算法的增长。。。例如，二次时间O（n2）等也是如此。甚至是通过阶乘增长的算法，如置换生成器，其O（n！）次。
例如，以下函数为O（n），因为算法与其输入n成比例增长：
f(int n) {
int i;
for (i = 0; i < n; ++i)
printf("%d", i);
}
类似地，如果存在嵌套循环，时间将为O（n2）。
但O（log n）到底是什么？例如，说一个完整的二叉树的高度是O（log n）是什么意思？
我确实知道（也许不是很详细）对数是什么，从这个意义上说：log10 100=2，但我不知道如何识别具有对数时间的函数。
当前回答
每次编写算法或代码时，我们都会尝试分析其渐近复杂性。它不同于它的时间复杂性。
渐近复杂度是算法执行时间的行为，而时间复杂度是实际执行时间。但有些人可以互换使用这些术语。
因为时间复杂度取决于各种参数。1.物理系统2.编程语言3.编码样式4.还有更多。。。。。。
实际执行时间不是一个很好的分析指标。
相反，我们将输入大小作为参数，因为无论代码是什么，输入都是相同的。因此，执行时间是输入大小的函数。
以下是线性时间算法的示例
线性搜索给定n个输入元素，要搜索数组中的元素，最多需要“n”个比较。换句话说，无论你使用什么编程语言，你喜欢什么编码风格，在什么系统上执行它。在最坏的情况下，它只需要n次比较。执行时间与输入大小成线性比例。
它不仅仅是搜索，无论是什么工作（增量、比较或任何操作），它都是输入大小的函数。
所以当你说任何算法都是O（logn）这意味着执行时间是输入大小n的log倍。
随着输入大小的增加，完成的工作（这里是执行时间）增加。（因此，比例）
n Work
2 1 units of work
4 2 units of work
8 3 units of work
随着输入大小的增加，所做的工作也会增加，并且与任何机器无关。如果你试图找出工作单位的价值它实际上取决于上述参数。它会根据系统和所有参数而改变。
其他回答
我可以补充一些有趣的东西，很久以前我在科尔曼等的书中读过。现在，想象一个问题，我们必须在问题空间中找到解决方案。这个问题空间应该是有限的。
现在，如果你能证明，在你的算法的每一次迭代中，你都切断了这个空间的一部分，这不小于某个极限，这意味着你的算法在O（logN）时间内运行。
我应该指出，我们这里讨论的是相对分数极限，而不是绝对分数极限。二进制搜索是一个经典的例子。在每一步中，我们都会丢掉1/2的问题空间。但二进制搜索并不是唯一的例子。假设，你以某种方式证明了，在每一步中，你至少丢掉了1/128的问题空间。这意味着，您的程序仍然以O（logN）时间运行，尽管比二进制搜索慢得多。这是分析递归算法的一个很好的提示。通常可以证明，在每一步递归都不会使用几个变量，这会导致问题空间中某些分数的截断。
我无法理解如何使用日志时间标识函数。
对数运行时间函数最常见的属性是：
选择下一个要执行某些操作的元素是多种可能性之一，并且只需要选择一个。
or
执行操作的元素是n的数字
这就是为什么，例如，在电话簿中查找人是O（logn）。你不需要检查电话簿上的每个人，就能找到合适的人；相反，你可以简单地根据他们的名字的字母顺序进行划分和征服，在每个部分中，你只需要探索每个部分的一个子集，就可以最终找到某人的电话号码。
当然，一本更大的电话簿仍然需要更长的时间，但它的增长速度不会像增加电话簿的比例那样快。
我们可以扩展电话簿示例，以比较其他类型的操作及其运行时间。我们将假设我们的电话簿中有具有唯一名称的业务（“黄页”）和可能没有唯一名称的人员（“白页”）。电话号码最多分配给一个人或一家公司。我们还将假设翻到特定页面需要恒定的时间。
以下是我们可能在电话簿上执行的一些操作的运行时间，从最快到最慢：
O（1）（在最坏的情况下）：给定企业名称所在的页面和企业名称，找到电话号码。O（1）（在一般情况下）：给定一个人的名字和他们的名字所在的页面，找到电话号码。O（log n）：给定一个人的名字，在书中你还没有搜索到的部分的中途随机抽取一个点，然后检查这个人的名字是否在这个点上，从而找到电话号码。然后在书中人名所在的部分重复这个过程。（这是对人名的二进制搜索。）O（n）：查找电话号码包含数字“5”的所有人。O（n）：给定一个电话号码，找到拥有该号码的人或企业。O（n log n）：打印机的办公室出现了混乱，我们的电话簿上的所有页面都以随机顺序插入。通过查看每一页上的名字，然后将该页放在新的空电话簿中的适当位置，修正顺序，使其正确。
对于以下示例，我们现在在打印机的办公室。电话簿等待邮寄给每位居民或企业，每个电话簿上都有一个标签，标明应该邮寄到哪里。每个人或企业都有一本电话簿。
O（n log n）：我们想让电话簿个性化，所以我们将在他们指定的副本中找到每个人或企业的名字，然后在电话簿中圈出他们的名字，并为他们的惠顾写一封简短的感谢信。O（n2）：办公室发生了一个错误，每个电话簿中的每个条目在电话号码末尾都有一个额外的“0”。取出一些白色，去掉每个零。O（n·n！）：我们准备好把电话簿装到码头上了。不幸的是，原本要装书的机器人已经失控了：它正在把书按随机顺序放在卡车上！更糟糕的是，它把所有的书都装到卡车上，然后检查它们的顺序是否正确，如果不正确，它就把它们卸下来，重新开始。（这是可怕的bogo类型。）O（nn）：你把机器人修好，这样它就能正确地装载东西。第二天，你的一个同事对你开了个玩笑，把装卸台机器人连接到自动打印系统上。每次机器人去装载一本原版书时，工厂打印机都会对所有的电话簿进行重复打印！幸运的是，机器人的错误检测系统足够复杂，当它遇到要加载的复制书时，它不会尝试打印更多的副本，但它仍然必须加载已打印的每一本原始和复制书。
我可以举一个for循环的例子，也许一旦掌握了这个概念，在不同的上下文中理解起来会更简单。
这意味着在循环中，步长呈指数增长。例如。
for (i=1; i<=n; i=i*2) {;}
该程序的O表示法的复杂性为O（log（n））。让我们尝试手动循环（n介于512和1023之间（不包括1024）：
step: 1 2 3 4 5 6 7 8 9 10
i: 1 2 4 8 16 32 64 128 256 512
尽管n介于512和1023之间，但只进行了10次迭代。这是因为循环中的步骤呈指数增长，因此只需要10次迭代就可以到达终点。
x的对数（到a的底）是a^x的反函数。这就像说对数是指数的倒数。
现在试着这样看，如果指数增长非常快，那么对数增长（相反）非常慢。
O（n）和O（log（n））之间的差异是巨大的，类似于O（n（n）与O（a^n）之间的区别（a是常数）。
你可以通过说时间与N中的位数成正比来直观地想到O（log N）。
如果一个操作对输入的每个数字或位执行恒定的时间工作，则整个操作所花费的时间将与输入中的数字或位的数量成比例，而不是与输入的大小成比例；因此是O（log N）而不是O（N）。
如果一个操作做出一系列恒定的时间决定，每个决定将要考虑的输入的大小减半（减少3、4、5…的因子），那么整个过程将花费与输入大小N的对数基2（基3、基4、基5…）成比例的时间，而不是O（N）。
等等
分治算法通常具有运行时间的logn成分。这来自于输入的重复减半。
在二进制搜索的情况下，每次迭代都会丢弃一半的输入。需要注意的是，在Big-O表示法中，log是以2为底的log。
编辑：如上所述，对数基数并不重要，但当推导算法的Big-O性能时，对数因子将来自减半，因此我认为它是基数2。
