一、大O表示法

大O表示法是一种特殊的表示法，指出了算法的速度有多快，指出了最糟情况下的运行时间。

O(n) 的意思是在最糟糕的情况下，n 为需要运行的次数。

log n^m 的意思是，要几个n 相乘才会得到m。

所以使用二分法，其速度为 O( log 2^m )，其中m 为元素个数总和。

1.1 一些常见的大O 运行时间

O(log n)，也叫对数时间，这样的算法包括二分查找。

O(n)，也叫线性时间，这样的算法包括简单查找。

O(n ＊ log n) 这样的算法包括快速排序 ——一种速度较快的排序算法。

O(n2)，这样的算法包括选择排序 ——一种速度较慢的排序算法。

O(n! )，这样的算法包括旅行商问题的解决方案 ——一种非常慢的算法。

在这里插入图片描述

二、选择排序法 O(n^2)

有一个数组，其中的内容是乱序的，请对其排序

a[ 10 ] = {10, 6 , 22, 23 ,40 ,0 ,1 ,8 , 7, 25};

使用选择排序的思路是，每次挑选最大或最小的数，依次放在一个新的数组中，这样时间复杂序为 O(n^2)。

因为，每个元素都要与其他元素比较一下。

代码实现如下：

a[10]= {
   10, 6 , 22, 23 ,40 ,0  ,1 ,8 , 7, 25};int * sort(int *a, int Size){
   	int *p = a;	int temp=0, k=0;	// 对当前数组中 n - 1 个元素进行遍历 	for(int i =0; i

其时间复杂度为：

当元素个数为n 时，需要比较 (n-1)*(n-1) 次，简化为O(n x n) = O(n^2)

转载地址：https://ciellee.blog.csdn.net/article/details/107243398 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：【经典算法实现 2】递归

下一篇：【LeetCode #7 题解】整数反转

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

一、大O表示法

1.1 一些常见的大O 运行时间

二、选择排序法 O(n^2)

发表评论

最新留言

关于作者

推荐文章