logn时间复杂度的算法

‘壹’ 时间复杂度log怎么算

如果程序运行的规模，每执行一次的规模是按等比例规模降低的，那么这个算法的时间复杂度就是logn的。

‘贰’ 堆排序和快排的平均时间复杂度为O(nlogn)，是怎么计算的呢

每次分成两堆，递归边界就是1，这个复杂度就是n*logn（底数为2）

‘叁’ 严蔚敏老师的《数据结构》里，关于时间复杂度的写法，譬如logn，这个对数函数的底数是多少啊

算法中log级别的时间复杂度都是由于使用了分治思想,这个底数直接由分治的复杂度决定。如果采用二分法,那么就会以2为底数,三分法就会以3为底数,其他亦然。不过无论底数是什么,log级别的渐进意义是一样的。也就是说该算法的时间复杂度的增长与处理数据多少的增长的关系是一样的。

(3)logn时间复杂度的算法扩展阅读：

时间复杂度的计算方法

（1）一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得T(n)/f(n)的极限值（当n趋近于无穷大时）为不等于零的常数，则称f(n)是T(n)的同数量级函数。

记作T(n)=O(f(n))，称O(f(n))
为算法的渐进时间复杂度，简称时间复杂度。

（2）在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级。

（3）在pascal中比较容易理解，容易计算的方法是：看看有几重for循环，只有一重则时间复杂度为O(n)，二重则为O(n^2)，依此类推，如果有二分则为O(logn)，二分例如快速幂、二分查找，如果一个for循环套一个二分，那么时间复杂度则为O(nlogn)。

‘肆’ i=1; while(i<=n) i=i*2 这个算法的时间复杂度怎么算

这个算法的时间复杂度为logn。

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。

并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f (n)，因此，算法的时间复杂度记做：T (n) =0 (f (n) )。随着模块n的增大，算法执行的时间的增长率和f (n)的增长率成正比，所以f (n)越小，算法的时间复杂度越低，算法的效率越高。

在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T (n)的同数量级。

(4)logn时间复杂度的算法扩展阅读

算法的时间性能分析

算法耗费的时间和语句频度

一个算法所耗费的时间=算法中每条语句的执行时间之和

每条语句的执行时间=语句的执行次数(即频度(Frequency Count))×语句执行一次所需时间

算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。

若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。

‘伍’ 如何计算一个算法的时间复杂度

你这个问题是自己想出来的吧？
第一，你指的时间复杂度是大o表示法的复杂度，也就是一个上界，但不是上确界，所以就算你以一种方式中断排序过程，时间复杂度还是o(n*logn)，假设排序过程还能执行的话。
第二，达到o(n*logn)的排序算法，以快速排序为例，快速排序不知道你看过没有，它不像选择排序或者冒泡排序那样，每一趟可以确定一直最大或者最小值，对于快速排序，每一趟排序后如果你删掉最后一个元素将导致整个算法失效。如果你要用这种删除元素方法的话，只能采用冒泡排序或者选择排序，时间复杂度是o(n^2)
所以，我猜想你是不是想做类似于在n个元素中寻找前k个最大者之类的事情（k=n-l）
如果是这样的话，有复杂度是o(n*logk)的算法，利用快速排序中的partition操作
经过partition后，pivot左边的序列sa都大于pivot右边的序列sb；
如果|sa|==k或者|sa|==k-1，则数组的前k个元素就是最大的前k个元素，算法终止;
如果|sa|
k，则从sa中寻找前k大的元素。
一次partition(arr,begin,end)操作的复杂度为end-begin，也就是o(n)，最坏情况下一次partition操作只找到第1大的那个元素，则需要进行k次partition操作，总的复杂度为o(n*k)。平均情况下每次partition都把序列均分两半，需要logk次partition操作，总的复杂度为o(n*logk)。
由于k的上界是n，所以以n表示的总复杂度还是o(n*logn)

‘陆’ 各种排序的时间复杂度

各种常用的算法，对时间复杂度的情况是这样。直接插入排序，是n平方的时间复杂度。直接选择排序是n平方的时间复杂度，冒泡排序也是n平方的时间复杂度。快速排序，希尔排序，和归并排序，都是n×(logn)的时间复杂度

‘柒’ 算法时间复杂度比较：根号n与logn相比哪个更优优多少试根据下图猜想其算法

米勒罗宾是logn的算法，但是实际应用上它并不稳定，一般在范围较大（int64范围）才会用，一般的情况用的都是sqrt(n)的算法，但是在需要判断大量素数的情况下（假设判断次数为m），一般是比较m*sqrt(n)和n的大小，如果前者小就暴力判断，否则用筛法会更快。

然后比较，在不考虑常数的情况下是logn更优，但是算法常数导致在数据较小的一些情况下sqrt(n)反而更快。

第一个根号n的：

#include<cmath>

inlineboolisPrime(intx){
if(x==2){returntrue;}
if(x<2){returnfalse;}
intpos=int(sqrt(x))+1;
for(inti=2;i<=pos;++i){
if(x%i==0){returnfalse;}
}
returntrue;
}

然后logn的米勒罗宾你可以看下博客网页链接

然后提供一个筛法的代码（stl版本）

#include<vector>

boolvis[MAXNUM];//MAXNUM就是最大数字
std::vector<int>primes;//储存素数

inlinevoidgetPrimes(intmaxn){
for(inti=2;i<=maxn;++i){
if(!vis[i]){primes.push_back(i);}
for(size_tj=0;j<primes.size()&&primes[j]*i<=maxn;++j){
vis[primes[j]*i]=true;
}
}
}

实际应用一般用筛法或者sqrt(n)算法，只有大数据才会用米勒罗宾

‘捌’ 如何计算时间复杂度

如何计算时间复杂度

定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数 T(n)称为这一算法的“时间复杂性”。

当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。

此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。

“大 O记法”：在这种描述中使用的基本参数是 n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。

这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。

O(1)

Temp=i;i=j;j=temp;

以 上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时 间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

O(n^2)

2.1. 交换i和j的内容
sum=0； （一次）
for(i=1;i<=n;i++) （n次 ）
for(j=1;j<=n;j++) （n^2次 ）
sum++； （n^2次 ）
解：T(n)=2n^2+n+1 =O(n^2)

2.2.
for (i=1;i<n;i++)
{
y=y+1; ①
for (j=0;j<=(2*n);j++)
x++; ②
}
解： 语句1的频度是n-1
语句2的频度是(n-1)*(2n+1)=2n^2-n-1
f(n)=2n^2-n-1+(n-1)=2n^2-2
该程序的时间复杂度T(n)=O(n^2).

O(n)

2.3.
a=0;
b=1; ①
for (i=1;i<=n;i++) ②
{
s=a+b;③
b=a;④
a=s;⑤
}
解： 语句1的频度：2,
语句2的频度： n,
语句3的频度： n-1,
语句4的频度：n-1,
语句5的频度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).

O(log2n )

2.4.
i=1; ①
while (i<=n)
i=i*2; ②
解： 语句1的频度是1,
设语句2的频度是f(n), 则：2^f(n)<=n;f(n)<=log2n
取最大值f(n)= log2n,
T(n)=O(log2n )

O(n^3)

2.5.
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
解： 当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).

我 们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最 坏情况运行时间是 O(n^2)，但期望时间是 O(nlogn)。通过每次都仔细 地选择基准值，我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中，精心实现的快速排序一般都能以 (O(nlogn)时间运行。
下面是一些常用的记法：

访问数组中的元素是常数时间操作，或说O(1)操作。一个算法 如 果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间 。常规的矩阵乘算法是O(n^3)，因为算出每个元素都需要将n对 元素相乘并加到一起，所有元素的个数是n^2。
指数时间算法通常来源于需要 求出所有可能结果。例如，n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的 。指数算法一般说来是太复杂了，除非n的值非常小，因为，在 这个问题中增加一个元素就导致运行时间加倍。不幸的是，确实有许多问题 (如着名 的“巡回售货员问题” )，到目前为止找到的算法都是指数的。如果我们真的遇到这种情况， 通常应该用寻找近似最佳结果的算法替代之。