Java教程

算法入门到进阶(一)——算法复杂度

本文主要是介绍算法入门到进阶(一)——算法复杂度,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 前言
  • 一、计算资源
    • 例题分析
      • 冒泡排序
      • 快速排序
      • 哈希算法
    • 算法的选择
  • 二、算法的定义
  • 算法的评估
  • 总结


前言

这个专栏我都是参考书籍《算法竞赛入门到进阶》,罗勇军、郭卫斌老师著进行编写的。
通过书籍上的材料以及自己的理解来撰写博客。

有不恰当的地方,欢迎各位朋友指正!

也非常欢迎各位hxd一起学习探讨。


一、计算资源

程序运行时需要两种资源,即计算时间和存储空间。资源是有限的,一个算法对这两个资源的使用程度可以用来衡量该算法的优劣。

  • 时间复杂度:程序运行需要的时间
  • 空间复杂度:程序运行需要的存储空间

通常用O来表示复杂度

通过下面这个例子来阐述复杂度的概念和影响
源码:

#include<iostream>
using namespace std;
int main() {
	int i, k=0, n = 1e8;
	clock_t start, end;
	start = clock();
	for (int i = 0; i < n; i++) {
		k++;
	}
	end = clock();
	cout << (double)(end - start) / CLOCKS_PER_SEC << endl;
}

分析:
在这里插入图片描述
运行结果:
在这里插入图片描述
所以可以看出,在n=1e8的时候,输出时间为0.135.
当n=1e9的时候
在这里插入图片描述输出时间为:1.313
那么我们如何来评定他的时间复杂度呢?
由于不同的计算机性能不同,所以不能直接把上面的时间作为时间复杂度。应该根据程序执行的次数来衡量才合理。
所以上面的程序执行了n次,那么时间复杂度就是O(n)。

例题分析

给出n个整数,按照从大到小的顺序输出其中前m大的数
输入样例:
5  3
3  -35    92  213  -644

输出样例:
213  92  3

下面用冒泡排序,快速排序,哈希3种算法进行编程

冒泡排序

#include<iostream>
using namespace std;
int a[10000001];//记录数字

int m, n;
void bubble_sort() {//冒泡排序,结果仍然放到数组a中
	int temp;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - i ; j++) {
			if (a[j] < a[j+1]) {
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
}
int main() {
	while (scanf_s("%d %d", &n, &m)!=EOF) {
		for (int i = 0; i <= n-2; i++) {
			scanf_s("%d ", &a[i]);
		}
		printf_s("OK\n");
		bubble_sort();

		for (int i = 0; i < m; i++) {
			printf_s("%d ", a[i]);
		}
		printf("\n");
	}
	return 0;
}

运行结果
在这里插入图片描述时间复杂度为O(n^2)

快速排序

快速排序是基于分治法的优秀排序算法。这里可以先直接用STL的sort()函数。它是改良的快速排序,称为“内省式排序”将上面的冒泡算法改为
sort(a,a+n);即可

哈希算法

哈希算法是一种以空间换时间的算法。本题的哈希思路是:在输入数字t的时候,在a[5000000+t]这个位置记录a[50000000+t]=1,在输出的时候逐个检查a[i],如果a[i]等于1,就表示这个数存在,打印前m个数

#include<iostream>
using namespace std;
const int MAX = 1000001;
int a[MAX];
int main() {
	int n, m;
	while (scanf_s("%d %d", &n, &m) != EOF) {
		memset(a, 0, sizeof(a));//将数组a清0
		for (int i = 0; i < n; i++) {
			int t; \
				scanf_s("%d", &t);
			a[500000 + t] = 1;//数字t,登记在500000+t这个位置
		}
		for (int i = MAX-1; m > 0; i--) {
			if (a[i]) {
				printf_s("%d ", i-500000);
				m--;
			}
		}
		printf_s("\n");
	}
	return 0;
}

运行结果:
在这里插入图片描述时间复杂度为O(n)

算法的选择

对于同一个问题总是有不同的解决办法,所以我们在实际开发中对算法的选择要从实际情况和空间,时间复杂度来考虑。

二、算法的定义

相信大家都知道**“程序=算法+数据结构”**,算法是解决问题的逻辑、方法、过程,数据结构是数据在计算机中的存储和访问方式,二者紧密结合。

算法是对特定问题求解步骤的一种描述,是指令的有限序列。它有下面5个特征

  1. 输入:一个算法有0个或多个输入。程序可以没有输入,例如一个定时闹钟程序,他不需要输入,但是能够每隔一段时间就输出一个警报。
  2. 输出:一个算法有一个或多个输出。程序可以没有输入但是一定要有输出。
  3. 有穷性:一个算法必须在执行有穷步之后结束,且每一步都在有穷时间内完成。
  4. 确定性:算法中的每一条指令必须有确切的含义,对于相同的输入只能得到相同的输出。
  5. 可行性:算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

算法的评估

衡量算法性能的主要标准是时间复杂度。

为什么不讨论空间复杂度呢?
在一般情况下,一个程序的空间复杂度是容易分析的,而时间复杂度往往关系到算法的根本逻辑,更能说明一个程序的优劣。

一个程序或算法的时间复杂度有以下几种可能

  1. O(1)
    计算时间是一个常数,和问题的规模n无关。例如用公式计算时,一次计算的复杂度就是O(1);哈希算法,用hash函数在常数时间内计算出存储位置;在矩阵A[M] [N]中查找第i行第j列的元素只需要访问A[i][j]就够了。
  2. O(log2n)

计算时间是对数,通常是以2为底的对数,每一步计算后,问题的规模减小一倍。例如在一个长度为n的有序数列中查找某个数,用折半查找的方法只需要log2n次就能找到。再如分治法,一般情况下,在每一个步骤把规模减小一倍,所以一共有O(log2n)个步骤。

  1. O(n)
    计算时间随规模n线性增长。在很多情况下,这是算法可能达到的最优复杂度,因为对输入n个数,程序一般需要处理所有的数,即计算n次。例如查找一个无序数列中的某个数,可能需要检查所有的数。再如图问题,有V个点和E个边,大多数图的问题都需要搜索到所有的点和边,复杂度的上限就是O(V+E)
  2. O(nlog2n)
    这常常是算法等达到的最优复杂度。例如分治法,一共O(log2n)个步骤,每一个步骤对每个数操作一次,所以复杂度是O(nlog2n)。用分治法思想实现的快速排序和归并排序算法复杂度就是O(nlog2n)
  3. O(n^2)
    一个两重循环的算法,复杂度就是O(n^2)。例如冒泡排序就是典型的两重循环。类似的复杂度还有O(n ^3),O(n ^4)等
  4. O(2^n)
    一般对应集合问题,例如一个集合中有n个数,要求输出它的所有子集,子集有2 ^n个
  5. O(n!)
    在排列问题中,如果要求输出所有的全排列,那么复杂度就是O(n!)。

上面的算法分为两类:

  1. 多项式复杂度:前5种
  2. 指数复杂度:后面2种

如果一个算法是多项式算法,就称它为“高效算法”;如果一个算法是指数复杂度,则称它为"低级算法"。多项式复杂度的算法随着规模的增加可以通过堆叠硬件来实现。但是指数型的没有办法。

问题规模和可用算法表(牢记)
在这里插入图片描述

总结

相信通过阅读上面的内容,你对算法的评估有了更加清晰地评估标准。

这篇关于算法入门到进阶(一)——算法复杂度的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!