如何求时间(如何求时间复杂度)

如何求时间复杂度

时间复杂度是指一个程序运行时所需要消耗的时间量级，也就是程序运行时根据输入的规模，所需的运行总时间规模，都是用数学公式来表示。一般指的是最坏时间复杂度。理由如下：

1、最坏时间复杂度，是在任意输入下的运行时间界限，保证算法任何时候运行时间都不会比其更长。

2、在某些算法上，最坏情况出现频繁。

3、在算法这样的事物上，平均和最坏一样很糟糕！

怎样求时间复杂度

当输入量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足够大以后，具有较慢上升函数的算法必然工作得更快。

计算时间复杂度的方法

时间复杂度是一个算法流程中，最差情况下常数操作数量的指标。

例子：一个有序数组A，另一个无序数组B，请打印B中所有不在A中的数。A数组长度为N，B数组长度为M。

第一种方法：B中每个数在A中遍历一下，输出所有不在A中的数。

A = list(map(int,input().split()))

B = list(map(int,input().split()))

N = len(A)

M = len(B)

for i in range(M):

j = 0

while j<N and B[i]!=A[j]:

j += 1

if j==N:

print(B[i])

1

2

3

4

5

6

7

8

9

10

11

12

1

2

3

4

5

6

7

8

9

10

11

12

第一种方法包含两个循环，对B遍历一遍，B中每个数又要在A中遍历一遍，因此时间复杂度为O ( M × N ) O(M\times N)O(M×N)。

第二种方法：B中每个数在A中二分找一下。

因A有序（假设升序），将A进行二分，分为left和right。中间位置的数为mid。将B中每个数先与mid相比较，如果B[i]比mid大，那么B[i]只可能在A的right，如果B[i]比mid小，那么B[i]只可能在left。每次砍一半的操作，时间复杂度为O ( log ⁡ 2 N ) O(\log_2N)O(log

2

​

N)，又对B中每个数遍历一次，故这个算法的时间复杂度为M × O ( log ⁡ 2 N ) M\times O(\log_2N)M×O(log

2

​

N)。

二分法的停止条件是左边界超过右边界，while L<=R，也不用担心mid在加加减减过程中越界。

A = list(map(int,input().split()))

B = list(map(int,input().split()))

N = len(A)

M = len(B)

def binSearch(A,b):

L = 0

R = len(A)-1

while L<=R:

mid = int((L+R)/2)

# 在A中找到b了，返回True

if b==A[mid]:

return True

# b比A[mid]小，说明b在左边

if b<A[mid]:

R = mid - 1

# b比A[mid]大，说明b在右边

if b>A[mid]:

L = mid + 1

# 没找到b，返回False

return False

for i in range(M):

flag = binSearch(A,B[i])

if not flag:

print(B[i])

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

第三种方法：先给B排序，然后用类似外排的方法打印不在A中的数。

关于排序算法之后单独介绍，对B排序后，在A,B均为有序数组。

在这里插入图片描述

a指针指向1，b指针指向3，当a<b时，a只能往后移动，当a=b时，b只能往后移动，当a>b时，打印b，同时b往后移。

（1）排序代价O ( M × log ⁡ M ) O(M\times\log M)O(M×logM) (2)打印数过程中，a最多指N NN个数，b最多指M MM个数，所以时间复杂度O ( N + M ) O(N+M)O(N+M)

因此整个算法时间复杂度O ( M × log ⁡ M ) + O ( N + M ) O(M\times\log M)+O(N+M)O(M×logM)+O(N+M) 。

停止条件是A或B数组已经到界了，如果A到界了，那么B[b,M-1]均需打印出来；如果B到界了，说明B数组里的数已经查找完了。

A = list(map(int,input().split()))

B = list(map(int,input().split()))

N = len(A)

M = len(B)

a = b = 0

while a<N and b<M:

if A[a]<B[b]:

a += 1

elif A[a]==B[b]:

b += 1

else:

print(B[b])

b += 1

while b<M:

print(B[b])

b += 1

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

排序算法

冒泡排序

算法思想：从小到大排。每次找到最大的数放在末位。

第一次看0，1位置比较大小，0位置比1位置大就交换。

第二次看1，2位置比较大小，1位置比2位置大就交换，依次进行下去，第一次遍历，最大的数会被排到最后。

第二次只需遍历0至end-1个数，因为最大的数已经到最后，然后重复第一步步骤，直到所有数被排好。

def BubbleSort(arr):

length = len(arr)

if not arr or length < 2:

return arr

for i in range(length,-1,-1):

for j in range(0,i-1):

if arr[j] > arr[j+1]:

tmp = arr[j]

arr[j] = arr[j+1]

arr[j+1] = tmp

return arr

1

2

3

4

5

6

7

8

9

10

11

1

2

3

4

5

6

7

8

9

10

11

常数操作次数为N + ( N − 1 ) + ( N − 2 ) + ⋯ + 2 + 1 N+(N-1)+(N-2)+\cdots+2+1N+(N−1)+(N−2)+⋯+2+1，所以算法时间复杂度为O ( N 2 ) O(N^2)O(N

2

)。

选择排序

算法思想：从小到大排。

第一步，从0到N-1位置找到最小的数放在[0]位置上。

第二步，从1到N-1位置找到最小的数放在[1]位置上。

…

如何确定最小的数？ 先找一个基准数，比基准数小的就互换，成为新的基准数。

def SelectionSort(arr):

length = len(arr)

if not arr or length < 2:

return arr

for i in range(length):

minNumber = arr[i]

for j in range(i+1,length):

if minNumber > arr[j]:

tmp = minNumber

minNumber = arr[j]

arr[j] = tmp

arr[i] = minNumber

return arr

1

2

3

4

5

6

7

8

9

10

11

12

13

1

2

3

4

5

6

7

8

9

10

11

12

13

算法时间复杂度为O ( N 2 ) O(N^2)O(N

2

)。

插入排序

算法思想：从小到大排。

每进来一个数，与它前面一个数比较，比前面的数小就交换，到了前一个位置后，在与前前位置的数比较大小，小就交换，大就停止。再进来一个数，按照上面的方法与前面的数交换插入。

def InsertSort(arr):

length = len(arr)

if not arr or length < 2:

return arr

for i in range(1,length):

j = i - 1

while j>=0:

if arr[j] > arr[j+1]:

tmp = arr[j]

arr[j] = arr[j+1]

arr[j+1] = tmp

j -= 1

else:

j = -1

return arr

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

插入排序的时间复杂度与数据状况有关。例如数组[1,2,3,4,5]整体有序，那么在计算时代价为O ( N ) O(N)O(N)，但如果是[5,4,3,2,1]要升序排列，那么代价就是O ( N 2 ) O(N^2)O(N

2

)，按最差情况计算，所以插入排序算法时间复杂度为O ( N 2 ) O(N^2)O(N

2

)。

归并排序

算法思想：将数组一分为二，分别把左侧和右侧部分排好序，然后再利用外排的方式将整体排好序。

左右排好序后，需要一个辅助数组，左右两边比较大小，将小的数依次填入辅助数组。额外空间复杂度为O(n)。

def MergeSort(arr):

length = len(arr)

if not arr or length < 2:

return arr

sortProcess(arr,0,length-1)

return arr

def sortProcess(arr,L,R):

if L==R:

return arr[L]

mid = (L+R)//2

sortProcess(arr,L,mid)

sortProcess(arr,mid+1,R)

merge(arr,L,mid,R)

def merge(arr,L,mid,R):

help = []

p1 = L

p2 = mid+1

while p1<=mid and p2<=R:

if arr[p1] < arr[p2]:

help.append(arr[p1])

p1 += 1

else:

help.append(arr[p2])

p2 += 1

while p1<=mid:

help.append(arr[p1])

p1 += 1

while p2<=R:

help.append(arr[p2])

p2 += 1

for i in range(len(help)):

arr[L+i] = help[i]

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

递过算法的时间复杂度计算有一个master公式：

T ( N ) = a × T ( N b ) + O ( N d ) T(N)=a\times T(\frac{N}{b})+O(N^d)

T(N)=a×T(

b

N

​

)+O(N

d

)

N b \frac{N}{b}

b

N

​

表示子过程的规模，a aa表示子过程的个数，O ( N d ) O(N^d)O(N

d

)表示除去调用子过程之外，剩余操作的时间复杂度。

当log ⁡ b a > d \log_ba>dlog

b

​

a>d时，算法复杂度为O ( N log ⁡ b a ) O(N^{\log_ba})O(N

log

b

​

a

)

当log ⁡ b a = d \log_ba=dlog

b

​

a=d时，算法复杂度为O ( N d × log ⁡ N ) O(N^d\times\log N)O(N

d

×logN)

当log ⁡ b a < d \log_ba<dlog

b

​

a<d时，算法复杂度为O ( N d ) O(N^d)O(N

d

)

归并排序将数据规模一分为二，分为左右两个子过程，即a = 2 , b = 2 a=2,b=2a=2,b=2，且外排时间复杂度为O ( N ) O(N)O(N)，d = 1 d=1d=1，所以为第二种情况。归并算法的时间复杂度为O ( N × log ⁡ N ) O(N\times\log N)O(N×logN)。

时间复杂度求和怎么算

高斯消元

我们知道：

[sum_{i=1}^{n}i=frac{n(n+1)}{2} ]

以及：

[sum_{i=1}^{n}i^2=frac{n(n+1)(2n+1)}{6} ]

以及：

[sum_{i=1}^{n}i^3=(sum_{i=1}^{n}i)^2=(frac{n(n+1)}{2})^2 ]

那我们可以猜想，自然数的(k)次幂和对应的公式是一个次数为(k+1)的没有常数项的多项式（实际上也是的）。

证明吗，暂时不会。。。

However，我们可以拿这个猜想做题。

设这个(k+1)次的多项式(f(x)=sum_{i=1}^{k+1}a_ix^i)

利用待定系数法，我们只需要知道(k+2)对((x,f(x)))，列出方程组就能解出所有的(a_i)，从而就能代入更大的(x)求出(f(x))。

由于解方程组需要用到高斯消元算法，时间复杂度是(O(k^3))，在(kleq 100)的范围内还是能无压力解决的。

总结

时间复杂度：(O(k^3))

空间复杂度：(O(k^2))

由于高斯消元时要在模意义下做除法，对于模数不是质数的情况无法适应，而且时间复杂度难以接受，不是一种较常用的方法。

第二类斯特林数

分析

定义(S(n,m))表示(n)个有差别的球放入m个无差别的盒子中的方案数，要求盒子不能为空。

容易得到下面的递推式：

[S(n,m)=S(n-1,m-1)+mS(n-1,m) ]

考虑新加入的球，要么放在新的盒子里，要么放在之前的盒子里。因为球是有差别的，所以放在任意一个盒子里的方案都是不一样的，因此(S(n-1,m))要乘上一个(m)。

要用它解决自然数幂和问题，还是要用到第二类斯特林数的一个性质：

[a^k=sum_{i=0}^{k}S(k,i)i!C_a^i ]

这个性质还是很好解释的，我们可以把(a^k)当做(k)个有差别的球，放入(a)个有差别的盒子的方案数，盒子可以为空。

那么我们就枚举(i)个盒子被放满了，(S(k,i))只保证了球有差别，乘以(i!)相当于给盒子编号，令盒子也有差别，最后乘上一个(C_a^{i})表示在(a)个盒子中选(i)个的方案数。

那么就可以开始化自然数幂求和的式子：

(sum_{a=1}^{n}a^k)

(=sum_{a=1}^{n}sum_{i=0}^{k}S(k,i)i!C_a^i)

两个sigma没有关联，我们可以交换枚举顺序：

(=sum_{i=0}^{k}S(k,i)i!sum_{a=1}^{n}C_a^i)

由于(a<i)时(C_a^{i}=0)，又可以化成：

(=sum_{i=0}^{k}S(k,i)i!sum_{a=i}^{n}C_a^i)

继续化简需要用到一个性质：

(sum_{a=i}^{n}C_a^i=C_{n+1}^{i+1})

证明考虑运用组合数递推公式即：

(C_i^j=C_{i-1}^j+C_{i-1}^{j-1})

(C_{n+1}^{i+1})

(=C_n^i+C_n^{i+1})

(=C_n^i+C_{n-1}^i+C_{n-1}^{i+1})

(=C_n^i+C_{n-1}^i+C_{n-2}^i+C_{n-2}^{i+1})

继续化下去就会得到：

(=sum_{a=i}^{n}C_a^i)

性质就得证了，上面的式子就化简为：

(=sum_{i=0}^{k}S(k,i)i!C_{n+1}^{i+1})

组合数有点麻烦，我们展开为阶乘形式：

(=sum_{i=0}^{k}S(k,i)i!frac{(n+1)!}{(i+1)!(n-i)!})

拆开((i+1)!=i!*(i+1))：

(=sum_{i=0}^{k}S(k,i)frac{(n+1)!}{(i+1)(n-i)!})

发现(frac{(n+1)!}{(n-i)!})其实是(i+1)个连续整数相乘，其中必有一个是(i+1)的倍数，因此式子一定取整数，就不用考虑模数的问题了。

那么直接枚举这(i+1)个连续的整数，得到了时间复杂度为(O(k^2))的算法。计算斯特林数和求自然数幂的复杂度都是(O(k^2))，总复杂度就是(O(k^2))。

Code

附带分解乘法黑科技

#include <cstdio>

#include <cstring>

typedef long long ll;

const int N = 2007;

ll k, n, p, s[N][N];

ll multi(ll a, ll b)

{

ll x1 = a / 1000000, x2 = a % 1000000, y1 = b / 1000000, y2 = b % 1000000;

return (x1 * 1000000 % p * y1 % p * 1000000 % p + x1 * 1000000 % p * y2 % p + y1 * 1000000 % p * x2 % p + x2 * y2 % p) % p;

}

ll solve(ll n)

{

if (n == 0) return 0;

ll ret = 0;

for (int i = 1; i <= k && i <= n; i++)

{

ll sum = s[k][i];

for (ll j = n - i + 1; j <= n + 1; j++)

if (j % (i + 1) == 0) sum = multi(sum, j / (i + 1));

else sum = multi(sum, j);

ret = (ret + sum) % p;

}

return ret;

}

int main()

{

scanf("%lld%lld%lld%lld", &k, &n, &p);

s[0][0] = 1;

for (int i = 1; i <= k; i++)

for (int j = 1; j <= i; j++)

s[i][j] = (s[i - 1][j - 1] + multi(j, s[i - 1][j])) % p;

printf("%lld

", solve(n) % p);

return 0;

}

总结

时间复杂度：(O(k^2))

空间复杂度：(O(k^2))

这种做法由于不用除法而适用于模数为任意数的情况，但是求斯特林数复杂度是(O(k^2))的，当(k)较大时不再适用。

如何求时间复杂度的方法

快速排序法的时间复杂度是nlogn（n×log以2为底n的对数）

拓展：

快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

附各种排序法的时间复杂度如下：

求时间复杂度公式

计算公式：T (n) = O(f(n))n为问题规模；T (n) 为时间复杂度；f(n)的增长率和程序执行时间的增长率相同；O表示程序执行时间的“阶”PS：一般求链表的时间复杂度都用估算的估算算法的时间复杂度的方法为:

1.多数情况下,求最深层循环内的简单语句(原操作)的重复执行的次数.

2.当难以精确计算原操作的执行次数时,只需求出它关于n的增长率或阶即可.

3.当循环次数未知(与输入数据有关),求最坏情况下的简单语句(原操作)的重复执行的次数.我这学期刚学完数据结构，我还有一些我们老师讲课的PPT。如果你要的话可以告诉我

如何求时间复杂度和空间复杂度

编程实现算法后，算法就是由一组语句构成，算法的执行效率就由各语句执行的次数所决定。一个算法花费的时间与算法中语句的执行次数成正比，哪个算法语句执行次数多，它花费的时间就多，把时间复杂度记为 T(n) ，一般情况下，算法的基本操作重复执行的次数是关于模块 n 的一个函数 f(n) ，因此，我们可以把算法的时间复杂度记做： T(n) = O(f(n)) 。

随着模块 n 的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。我们研究复杂度的目的是要比较两个算法的效率的高低，并不需要仔细地分析这个算法比那个算法多几次运算那么清，所以我们采用渐近复杂度分析来比较算法的效率。我们在分析算法的时间复杂度时，一般都会规定各种输入情况得出最好情况下 T_{max}(n) 、最坏情况下 T_{min}(n) 和平均情况下 T_{avg}(n) 。

1. 求绝对值

我们需要求一个整数的绝对值，在算法设计上，只需要输入的值为负数时，返回它的相反数，其他情况返回本身，代码如下：

public static int abs(int a) {

return a < 0 ? -a : a;

}

该代码中只有一条运算指令语句，时间复杂度为 O(1) 。

2. 数组求和

已知一个整型数组，需要对数组内所有元素求和，如果只是通过遍历所有元素而不使用其他方法进行求和，可以使用如下代码实现：

public static int sum(int[] a) {

int s = 0;

for (int i : a) {

s += i;

}

return s;

}

由代码可知，如果输入数组的大小为 n ，执行语句中初始化赋值需要时间 O(1) ，循环语句中的赋值操作需要时间为 O(1)*n ，所以语句执行的时间为： O(1)+O(1)*n=O(n+1)=O(n) 。

3. 二分查找

已知一个有序数组，需要在数组中找到某个元素的位置，我们可以通过二分法来实现，代码如下：

public static int binarySearch(int[] a, int b) {

int i, r = 0, l = a.length;

while (r <= l) {

如何求时间复杂度用主方法

我来举个例子说明比如一种排序算法的时间复杂度是 O(N),那么运行时间就是正比于要素个数N,另一种排序算法的时间复杂度是O(N*LogN)，那么运行时间就正比于N*LogN所以N足够大的情况下，总是第一种算法快.但是，如果N不是很大，那么具体的运算时间并不一定都是前一种算法快，比如刚才的第一种算法的实际速度是 100×N， 第二种算法的实际速度是 2× N × LogN，N=100,就会是第二种算法快

求时间复杂度的三个方法

频度就是语句执行的次数，这个问题是： 时间复杂度就是将频度趋于无穷大时的阶次，忽略掉低次和常量，这个问题就是O(n^2)，即平方阶次的

求时间复杂度并写出分析过程

常见的复杂度计算公式有时间复杂度和空间复杂度，常用的技巧有大O表示法、时间复杂度递推公式和渐进分析法等。

1. 时间复杂度

时间复杂度是指算法运行所需时间与输入规模之间的关系。通常用大O表示法表示，即T(n)=O(f(n))，其中T(n)表示算法运行的时间复杂度，f(n)表示输入规模n的函数。常用的时间复杂度分类有以下几种：

- 常数阶O(1)：算法的运行时间与输入规模无关。

- 对数阶O(logn)：算法的运行时间与输入规模的对数成正比。

- 线性阶O(n)：算法的运行时间与输入规模成正比。

- 线性对数阶O(nlogn)：算法的运行时间与输入规模的对数乘以线性成正比。

- 平方阶O(n^2)：算法的运行时间与输入规模的平方成正比。

- 立方阶O(n^3)：算法的运行时间与输入规模的立方成正比。

- 指数阶O(2^n)：算法的运行时间与输入规模的指数成正比。

- 阶乘阶O(n!)：算法的运行时间与输入规模的阶乘成正比。

如何求时间复杂度的公式

高斯求和公式：和=（数列首项+数列末项）项数2，末项=首项+（项数-1）公差，项数=（末项-首项）公差+1，首项=末项-（项数-1）公差。

用数学表达式表示为假设数列为等差数列，为这个等差数列的和，d为这个等差数列的公差，n表示这个等差数列的项数，，则有以下公式：

高斯求和公式（即d=1时）有：

=（）n

=+(n-1)

n=（）+1

=-n+1

【例题】求1+2+3+...+200的值。

1+2+3+...+200

=（1+200）200

=20100

等差数列求和公式

假设数列为等差数列，为这个等差数列的和，d为这个等差数列的公差（d1），n表示这个等差数列的项数，，则有以通用下公式：

=+（n-1)d

n=+1

-(n-1)d

=n+n（n-1）d

【例题】求10，20，30，40，50，...，1000的和。

解析：从题中可以知道这个数列的公差为10，首先项为10，末项为1000，

项数n=（1000-10）10+1=100。

则有=100+100（100-1）10=50500