C++中的时间复杂度O（1）与O（n）有什么区别

Question

C++中的时间复杂度O（1）与O（n）有什么区别
for(int i=0;i<1000;i++)与for(int i=0;i<n;i++) 其中n是用户输入的
这两个有什么不一样
常数 n
for(int i=0;i<1000;i++) for(int i=0;i<n;i++) 用户输入1000
for(int i=0;i<10000;i++) for(int i=0;i<n;i++) 用户输入10000
for(int i=0;i<10000;i++) for(int i=0;i<n;i++) 用户输入100000
我认为这两个还是成线形比 而不是O（1）成常数比， O（n）成线形比

Answer 1

C++中的时间复杂度O（1）与O（n）的主要区别在于：

1、时间复杂度O（1）是常数阶，其基本操作重复执行的次数是一个固定的常数，执行次数不存在变化；

2、而时间复杂度O（n）是线性阶，其基本操作重复执行的次数是与模块n成线性相关的，其值会随着模块n的变化而变化，当模块n的规模确定为定值后，其时间复杂度转化为O（1）。

扩展资料

1.时间复杂度的计算方法：

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

例如：某算法的执行次数为  ，根据T（n）的数量级，则有  ，然后根据 T(n)/f(n) 求极限可得到常数c，则该算法的时间复杂度：T(n) = O(n^3) 。

2、常见的时间复杂度有：常数阶O(1)，对数阶O(  )，线性阶O(n)，线性对数阶O(nlog2n)，平方阶O(n^2)，立方阶O(n^3)等。

参考资料：百度百科：时间复杂度

Answer 2

你理解错了，我举个例子：
你设计了一个字符串类：客户有时需要知道字符串的长度,
所以有两种设计GetLength（）函数的方法
1。每次客户询问长度，你都用循环检测串长，即
for(i=0;str[i]!=0;++i)
这样效率低 时间复杂度O(n)
2 每次串内容改变时才算长度，算好后存起来，以后
客户需要知道字符串的长度就直接把变量值返回
这样效率高 时间复杂度O(1)

Answer 3

O(1)复杂度是与输入数据无关，O(n)是与输入数据成正比。
对于程序A，for(int i=0;i<1000;i++)，当输入任意的n时循环次数均为1000，复杂度为O(1)；
对于程序B，for(int i=0;i<n;i++)，当输入任意的n时循环次数为n，复杂度为O(n)。

Answer 4

时间复杂度是一个函数，它定量描述了该算法的运行时间。常见的时间复杂度有以下几种。
1，log(2)n，n，n log(2)n ，n的平方，n的三次方，2的n次方，n!

1指的是常数。即，无论算法的输入n是多大，都不会影响到算法的运行时间。这种是最优的算法。而n！（阶乘）是非常差的算法。当n变大时，算法所需的时间是不可接受的。

用通俗的话来描述，我们假设n=1所需的时间为1秒。那么当n = 10，000时。
O（1）的算法需要1秒执行完毕。
O（n）的算法需要10，000秒 ≈ 2.7小时 执行完毕。

O（n2）的算法需要100，000，000秒 ≈ 3.17年 执行完毕。
O（n！）的算法需要XXXXXXXX(系统的计算器已经算不出来了)。
可见算法的时间复杂度影响有多大。

所以O（1）和O（n）差了2.7小时，区别显而易见。