首页 > 编程语言 >算法复杂度之时间复杂度

算法复杂度之时间复杂度

时间:2024-09-28 21:48:58浏览次数:8  
标签:示例 int 复杂度 算法 时间 运行

一 . 数据结构前言

1.1 数据结构

数据结构(Data structure) 是计算机存储,组织数据的方式,指互相之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用,所以要学习各式各样的数据结构,如:线性表,树,图,哈希等。(不仅能存储数据,还能够管理数据)

1.2 算法

算法 ( Algorithm) : 就是定义良好的计算过程 , 取一个或一组的值输入,并产生处一个或一组值作为输出 。 一系列的计算步骤 , 用来将输入数据转化成输出结果)

数据结构和算法不分家 ----> 数据存储在内存中 , 需要有算法 ; 有算法的地方 ,需要存储和管理数据(数据结构);

二 . 算法效率

如何衡量一个算法的好坏 ?    ---->  代码简洁?时间短?

看以下例题 :

旋转数组  :  . - 力扣(LeetCode) 

void rotate(int* nums, int numsSize, int k) {
    while (k--) {
        int end = nums[numsSize-1];
        for (int i = numsSize-1; i > 0; i--) {
            nums[i] = nums[i - 1];
        }
        nums[0] = end;
    }
}

 代码测试可以通过 , 但是点击提交的时候却无法通过 ,在面对大量的数据 , 超出了时间限制  ,就说明这个算法 , 还不太好 , 那该怎样去衡量一个算法的好坏呢 ?

算法在编写成可执行程序后 , 运行时需要耗费时间资源和空间(内存资源)。这么看来 ,衡量一个算法的好坏 , 一般是从时间和空间两个维度来衡量 ,即时间复杂度和空间复杂度

时间复杂度主要衡量一个算法的运行快慢 。 而空间复杂度主要衡量一个算法运行所需要的额外空间 。

在计算机发展早期 , 计算机的存储容量很小 。 所以对空间复杂度很是在乎 。 但是经过计算机行业的迅速发展 , 计算机的存储容量已经达到了很高的程度 ,而对算法空间复杂度的关注度有所下降

三 . 时间复杂度 

定义 : 在计算机科学中 , 算法的时间复杂度是一个函数式 T(N) , 它定量描述了该算法的运行时间 。 时间复杂度是衡量程序的时间效率 , 那么为什么不去计算程序的运行时间呢? 

使用clock 函数计算时间 代码如下: 

#include <stdio.h>
#include <time.h>
int main()
{
	int t1 = clock();//当前时间
	//程序运行到当前程序的一个时间
	for (int i = 0; i < 100000; i++)
	{
		for (int j = 0; j < 100000; j++)
		{
			int a = 1;
		}
	}
	int t2 = clock();
	printf("%d\n", t2 - t1);
	return 0;
}

三次执行的时间都不相同 , 程序执行的时间不仅和编译器有关 , 而且还和CPU 的计算速度有关 ,并不能准确的计算出算法的运行的时间 

为什么不去计算程序的运行时间呢?

  1. 因为程序运行时间和编译环境和运行机器的配置都有关系 , 比如同一个算法程序 , 用一个老编译器 和 新编译器编译 , 在同样机器下运行时间不同。
  2. 同一个算法程序 ,用一个老低配置机器和新高配置机器 , 运行时间也不同。
  3. 并且时间只能程序写好后测试 , 不能写程序之前通过理想思想计算来评估。

时间复杂度是一个函数式 T(N) 到底是什么  

 思考:

 所以只需要计算程序能代表增长量的大概执行次数 ,复杂度的表示通常使用   大O的渐进表示法;

3.1 大O的渐进表示法:

大 O 符号 (Big O notation) : 是用于描述函数渐进行为的数学符号

推导大O阶规则:

  1. 时间复杂度函数时T(N) 中 ,只保留最高阶的项 , 去掉最低阶的项 ;  因为N不断变大,低阶项对结果影响越来越小 , 但N无穷大时 , 就可以忽略不计了。
  2. 如果高阶项存在   并且系数不是1 , 则可以去掉这个项目的常数项系数 , 因为当N不断增大的时候,这个系数对结果的影响越来越小,当N无穷大的时候,就可以忽略不计了。
  3. T(N) 中如果没有N相关的项目 , 只有常数项 , 用常数项1取代所有加法常数

所以  , 以上例题的时间复杂度是  O(n^2) 

3.2 示例1:

 3.3 示例2:

3.4 示例3:

3.5 示例4:

 在有些算法的时间复杂度存在最好 , 平均 ,和最坏情况

最坏情况 : 任意输入规模的最大运行次数(上界)

平均情况 : 任意输入规模的期望运行次数

最好情况 : 任意输入规模的最小运行次数(下界)

大O的渐进表示法在实际中一般情况关注的是算法的上界 , 也就是最坏运行情况。

 3.5 示例5:

3.6 示例6:

 

3.7 示例7: 

标签:示例,int,复杂度,算法,时间,运行
From: https://blog.csdn.net/khjjjgd/article/details/142593073

相关文章

  • 时间技能物品竞品抢拍拍卖发布h5公众号小程序开源版开发
    时间技能物品竞品抢拍拍卖发布h5公众号小程序开源版开发利用新型营销方式,将闲置的物品通过拍卖,让价格一提再提让用户趣在其中,营造一种不一样的购物体验!拍卖列表页列表页采用多分类,广告轮播及流动公告和拍卖商品列表组成商品列表包含了拍品基本信息以及状态和参与人数,另有当前拍品......
  • 精通推荐算法31:行为序列建模之ETA — 基于SimHash实现检索索引在线化
    1 行为序列建模总体架构2SIM模型的不足和为什么需要ETA模型SIM实现了长周期行为序列的在线建模,其GSU检索单元居功至伟。但不论Hard-search还是Soft-search,都存在如下不足:GSU检索的目标与主模型不一致。Hard-search通过类目属性来筛选历史行为,但不同类目不代表相关度低,比......
  • 关于算法复杂度
    1.复杂度的概念算法在编写成可执⾏程序后,运⾏时需要耗费时间资源和空间(内存)资源。因此衡量⼀个算法的好坏,⼀般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。    时间复杂度主要衡量⼀个算法的运⾏快慢,⽽空间复杂度主要衡量⼀个算法运⾏所......
  • 无人机之视觉导航算法篇
    一、图像采集与预处理图像采集:无人机通过其搭载的摄像头或其他视觉传感器实时采集周围环境的图像信息。图像预处理:对采集到的图像进行预处理,包括滤波、降噪、增强等操作,以提高图像的质量和清晰度,为后续的特征提取和匹配奠定基础。二、特征提取与匹配特征提取:从预处理后的图......
  • 算法训练营第三天| 203.移除链表元素、707.设计链表、206.反转链表
    203.移除链表元素状态:完成个人思路:首先令head符合条件,之后判断这个head是否为空,空的话返回空节点;非空的话继续进行。令pre=head;cur=head->next,只要cur非空,就判断cur的值的情况,如果需要删除,就改变pre->next和cur;如果不需要删除就继续检查下一个。看完讲解视频之后的想法:我......
  • 算法训练营第二天| 209.长度最小的子数组、59.螺旋矩阵II
    209.长度最小的子数组状态:没写出来->确认自己的想法是对的之后写出来了!!!初始思路:因为子数组是连续的,所以可以采用滑动窗口,我把这个窗口设置为左闭右闭,所以初始左右边界为0。之后先移动右指针,使得找到第一个和大于等于target的子数组,记录其长度,之后再移动左指针一位,再找第二个......
  • java基于协同过滤算法的springboot的煤矿员工健康管理系统(源码+文档+调试+vue+前后端
    收藏关注不迷路!!......
  • Dijkstra算法详解【附算法代码与运行结果】
    算法背景Dijkstra算法是一种用于在加权图中找到单个源点到所有其他顶点的最短路径的算法。这种算法由荷兰计算机科学家艾兹格·戴克斯特拉(EdsgerW.Dijkstra)在1956年提出。它适用于有向图和无向图,并且图中的边权重必须是非负数。基本原理如下图所示,找到一条从v1(节点1)到v6(......
  • 代码随想录算法训练营第三天 | 熟悉链表
    链表的存储方式数组是在内存中是连续分布的,但是链表在内存中可不是连续分布的。链表是通过指针域的指针链接在内存中各个节点。所以链表中的节点在内存中不是连续分布的,而是散乱分布在内存中的某地址上,分配机制取决于操作系统的内存管理。链表的定义template<typenameT>......
  • 【机器学习】ID3、C4.5、CART 算法
    目录常见的决策树算法1.ID32.C4.53.CART决策树的优缺点优点:缺点:决策树的优化常见的决策树算法1.ID3ID3(IterativeDichotomiser3)算法使用信息增益作为特征选择的标准。它是一种贪心算法,信息增益表示按某特征划分数据集前后信息熵的变化量,变化量越大,表示使用该......