我正在学习大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，但我不知道如何识别具有对数时间的函数。
当前回答
O（logN）基本上意味着时间线性上升，而N指数上升。因此，如果计算10个元素需要1秒，则计算100个元素需要2秒，计算1000个元素需要3秒，依此类推。
当我们进行分而治之的算法（如二进制搜索）时，它是O（logn）。另一个例子是快速排序，每次我们将数组分成两部分，每次都需要O（N）时间才能找到一个枢轴元素。因此，N O（log N）
其他回答
每次编写算法或代码时，我们都会尝试分析其渐近复杂性。它不同于它的时间复杂性。
渐近复杂度是算法执行时间的行为，而时间复杂度是实际执行时间。但有些人可以互换使用这些术语。
因为时间复杂度取决于各种参数。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）是衡量任何代码运行时性能的多项式时间复杂度之一。
我希望你已经听说过二进制搜索算法。
假设您必须在大小为N的数组中找到一个元素。
基本上，代码执行如下N不适用于2不适用于4N/8…等
如果你把每一级所做的所有工作相加，你将得到n（1+1/2+1/4….），等于O（logn）
首先，我建议您阅读以下书籍：；
算法（第4版）
下面是一些函数及其预期的复杂性。数字表示语句执行频率。
以下Big-O复杂性图表也取自bigocheatsheet
最后，非常简单的展示展示了它是如何计算的；
剖析程序的语句执行频率。
分析程序的运行时间（示例）。
简单地说：在算法的每一步，你都可以将工作减半。（渐近等价于第三、第四、…）
概述
其他人已经给出了很好的图表示例，例如树形图。我没有看到任何简单的代码示例。因此，除了我的解释，我还将提供一些带有简单打印语句的算法，以说明不同算法类别的复杂性。
首先，你需要对对数有一个大致的了解，你可以从https://en.wikipedia.org/wiki/Logarithm . 自然科学使用e和自然日志。工程弟子将使用log_10（对数基数10），计算机科学家将大量使用log_2（对数基数2），因为计算机是基于二进制的。有时你会看到自然log的缩写为ln（），工程师通常不使用_10，只使用log（），log_2缩写为lg（）。所有类型的对数都以类似的方式增长，这就是为什么它们共享相同的log（n）类别。
当您查看下面的代码示例时，我建议您先查看O（1），然后查看O（n），然后再查看O（n^2）。在你擅长这些之后，再看看其他的。我已经包含了干净的示例和变体，以证明细微的变化仍然可以导致相同的分类。
你可以把O（1）、O（n）、O（logn）等看作是增长的类或类别。有些类别要比其他类别花费更多的时间。这些类别有助于我们对算法性能进行排序。有些随着输入n的增长而增长得更快。下表以数字形式显示了上述增长。在下表中，将log（n）视为log_2的上限。
各种大O类别的简单代码示例：
O（1）-恒定时间示例：
算法1：
算法1打印一次hello，它不依赖于n，所以它总是在恒定的时间内运行，所以它是O（1）。
print "hello";
算法2：
算法2打印hello 3次，但它不取决于输入大小。即使随着n的增长，该算法也将始终只打印hello 3次。也就是说，3是一个常数，所以这个算法也是O（1）。
print "hello";
print "hello";
print "hello";
O（log（n））-对数示例：
算法3-其行为类似于“log_2”
算法3演示了在log_2（n）中运行的算法。注意for循环的后操作将i的当前值乘以2，因此i从1到2到4到8到16到32。。。
for(int i = 1; i <= n; i = i * 2)
print "hello";
算法4-其行为类似于“log_3”
算法4证明了log_3。注意我从1到3到9到27。。。
for(int i = 1; i <= n; i = i * 3)
print "hello";
算法5-其行为类似于“log_1.02”
算法5很重要，因为它有助于表明，只要数字大于1，并且结果与自身重复相乘，那么你就在看对数算法。
for(double i = 1; i < n; i = i * 1.02)
print "hello";
O（n）-线性时间示例：
算法6
这个算法很简单，可以打印n次hello。
for(int i = 0; i < n; i++)
print "hello";
算法7
该算法显示了一种变体，它将打印hello n/2次。n/2=1/2*n。我们忽略1/2常数，看到这个算法是O（n）。
for(int i = 0; i < n; i = i + 2)
print "hello";
O（n*log（n））-log（n）示例：
算法8
将其视为O（log（n））和O（n）的组合。for循环的嵌套帮助我们获得O（n*log（n））
for(int i = 0; i < n; i++)
for(int j = 1; j < n; j = j * 2)
print "hello";
算法9
算法9类似于算法8，但每个循环都允许变化，这仍然导致最终结果为O（n*log（n））
for(int i = 0; i < n; i = i + 2)
for(int j = 1; j < n; j = j * 3)
print "hello";
O（n^2）-n平方示例：
算法10
O（n^2）很容易通过循环的嵌套标准获得。
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
print "hello";
算法11
类似于算法10，但有一些变化。
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j = j + 2)
print "hello";
O（n^3）-n立方示例：
算法12
这类似于算法10，但有3个循环而不是2个。
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
print "hello";
算法13
类似于算法12，但具有一些仍然产生O（n^3）的变化。
for(int i = 0; i < n; i++)
for(int j = 0; j < n + 5; j = j + 2)
for(int k = 0; k < n; k = k + 3)
print "hello";
总结
上面给出了几个直接的例子和变化，以帮助说明可以引入哪些细微的变化，而这些变化实际上不会改变分析。希望它能给你足够的洞察力。
