乐趣区

关于数据结构:时间复杂度的实例

前言

此文章是对于工夫复杂度的


提醒:以下是本篇文章正文内容,上面案例可供参考

一、工夫复杂度是什么?

工夫复杂度的定义:在计算机科学中,算法的工夫复杂度是一个函数,它定量形容了该算法的运行工夫。一个算法执行所消耗的工夫,从实践上说,是不能算进去的,只有你把你的程序放在机器上跑起来,能力晓得。然而咱们须要每个算法都上机测试吗?是能够都上机测试,然而这很麻烦,所以才有了工夫复杂度这个剖析形式。一个算法所破费的工夫与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的工夫复杂度。
大白话来说就是:这个算法最高跑了多少次。不懂?没关系,上面咱们看具体例子,每个例子都有他的特色,可能会打断你上一条的想法,而后你就明确工夫复杂度是个什么货色。

二、实体展现

1. 工夫复杂度为 1

void Func4(int N) {
 int count = 0;
 for (int k = 0; k < 100; ++ k)
 {++count;}
 printf("%d\n", count);
}

工夫复杂度为 1,是执行常数次的意思,CPU 一秒能运行上亿次,这些数字不过尔尔,你的 int 又能有多大。
所以这里尽管运行 100 次,然而工夫复杂度为 1。

2. 工夫复杂度为 N^2

代码如下(示例):

// 请计算一下 Func1 中 ++count 语句总共执行了多少次?void Func1(int N) {
int count = 0;
for (int i = 0; i < N ; ++ i) {for (int j = 0; j < N ; ++ j)
 {++count;}
}
 
for (int k = 0; k < 2 * N ; ++ k) {++count;}
int M = 10;
while (M--) {++count;}

Func1 执行的基本操作次数:

    F(N)=N^2+2*N+10;

理论中咱们计算工夫复杂度时,咱们其实并不一定要计算准确的执行次数,而只须要大略执行次数,那么这里咱们应用大 O 的渐进表示法(这个就是取最高阶的)。
这里咱们就取 N^2。

3. 工夫复杂度还是为 N^2

void BubbleSort(int* a, int n) {assert(a);
 for (size_t end = n; end > 0; --end)
 {
 int exchange = 0;
 for (size_t i = 1; i < end; ++i)
 {if (a[i-1] > a[i])
 {Swap(&a[i-1], &a[i]);
 exchange = 1;
 }
 }
 if (exchange == 0)
 break;
 }
}

咱们来看最坏执行了 N *(N+1)/2,最高阶是多少是 N^2,其余的 1 /2,N/2,通通不要了。

4. 工夫复杂度为 M +N

代码如下(示例):

void Func3(int N, int M) {
 int count = 0;
 for (int k = 0; k < M; ++ k)
 {++count;}
 for (int k = 0; k < N ; ++ k)
 {++count;}
 printf("%d\n", count);
}

因为 M 和 N 不是一个未知数,所以不能合并,是不是又认知到了什么。

5. 工夫复杂度为 N

void Func2(int N) {
 int count = 0;
 for (int k = 0; k < 2 * N ; ++ k)
 {++count;}
 int M = 10;
 while (M--)
 {++count;}
 printf("%d\n", count);
}

看清楚了 M 是 10,不是未知数。

6. 工夫复杂度为 logN

int BinarySearch(int* a, int n, int x) {assert(a);
 int begin = 0;
 int end = n-1;
 // [begin, end]:begin 和 end 是左闭右闭区间,因而有 = 号
 while (begin <= end)
 {int mid = begin + ((end-begin)>>1);
 if (a[mid] < x)
 begin = mid+1;
 else if (a[mid] > x)
 end = mid-1;
 else
 return mid;
 }
 return -1; }

这个代码是数学上二分法的实现,就不停得除二,执行多少次呢,log2(N),所以这类的工夫复杂度为 logN。

三、总结

这么看来工夫复杂度就那么几个式子

退出移动版