算法的时间复杂度和空间复杂度

简介: 1.1如何衡量一个算法的好坏衡量一个算法的好坏一般从两个维度来考虑,一个是时间复杂度,一个是空间复杂度。时间复杂度是主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法所需要的额外空间。2.时间复杂度2.1时间复杂度的概念时间复杂度:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。为了简化计算时间复杂度的方法,我们可得,一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作执行次数为算法的时间复杂度。

1.算法效率


1.1如何衡量一个算法的好坏


衡量一个算法的好坏一般从两个维度来考虑,一个是时间复杂度,一个是空间复杂度。


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


2.时间复杂度


2.1时间复杂度的概念


时间复杂度:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。为了简化计算时间复杂度的方法,我们可得,一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作执行次数为算法的时间复杂度。


所以:找出某条基本语句和问题规模 N 之间的数学表达式就是该算法的时间复杂度。

例:

void FUNC(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 = 20;
  while (m--) {
    count++;
  }
}


FUNC函数执行的次数:


593dd6068d73497a9f80e9b054ab9c81.png


在实际中我们计算时间复杂度不需要太精确,采用大O的渐进估算方法,取运行时间函数的最高项,去除与这个最高项相乘的常数,只有常数项就是O1。计算时间复杂度要算最坏的那一个。


3.空间复杂度


3.1空间复杂度的概念:


空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用储存空间的量度。和时间复杂度一样采用大 O的计算方法。


注意:函数运行时所需要的栈空间在编译期间就已经确定好了,因此空间复杂度主要由函数在运行的时候额外申请的空间来确定。我一般就看他额外申请了多少空间(常见有malloc函数动态额外申请空间),递归的话递归多少次就开辟了多少个栈,空间复杂度就为 O(N)。


4. 常见的复杂度对比


4c189400261646a499ff84ef5a40a9eb.png

目录
相关文章
|
2月前
|
机器学习/深度学习 缓存 算法
Python算法设计中的时间复杂度与空间复杂度,你真的理解对了吗?
【10月更文挑战第4天】在Python编程中,算法的设计与优化至关重要,尤其在数据处理、科学计算及机器学习领域。本文探讨了评估算法性能的核心指标——时间复杂度和空间复杂度。通过详细解释两者的概念,并提供快速排序和字符串反转的示例代码,帮助读者深入理解这些概念。同时,文章还讨论了如何在实际应用中平衡时间和空间复杂度,以实现最优性能。
72 6
|
4月前
|
机器学习/深度学习 算法 程序员
读《趣学算法》:重开算法之门,时间复杂度与空间复杂度
本文是作者阅读《趣学算法》后的笔记,介绍了算法复杂度的基本概念,包括时间复杂度和空间复杂度的不同阶表示,并通过具体例子展示了如何计算和理解算法的效率。
68 2
读《趣学算法》:重开算法之门,时间复杂度与空间复杂度
|
2月前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
2月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
38 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
2月前
|
存储 算法
算法的时间复杂度和空间复杂度
本文详细讨论了算法的时间复杂度和空间复杂度,包括它们的概念、计算方法和常见复杂度的对比,并通过多个实例解释了如何计算算法的时间和空间复杂度。
116 0
算法的时间复杂度和空间复杂度
|
2月前
|
机器学习/深度学习 存储 算法
【初阶数据结构】算法效率大揭秘 | 时间与空间复杂度的深度剖析
【初阶数据结构】算法效率大揭秘 | 时间与空间复杂度的深度剖析
|
3月前
|
算法 Python
震惊!Python 算法设计背后,时间复杂度与空间复杂度的惊天秘密大起底!
在 Python 算法设计中,理解并巧妙运用时间复杂度和空间复杂度的知识,是实现高效、优雅代码的必经之路。通过不断地实践和优化,我们能够在这两个因素之间找到最佳的平衡点,创造出性能卓越的程序。
40 4
|
3月前
|
缓存 算法 数据处理
时间&空间复杂度,Python 算法的双重考验!如何优雅地平衡两者,打造极致性能?
在Python算法中,时间与空间复杂度的平衡至关重要。时间复杂度反映算法执行时间随输入规模的变化趋势,空间复杂度则关注额外存储空间的需求。优秀的算法需兼顾两者,如线性搜索时间复杂度为O(n),空间复杂度为O(1);二分查找在时间效率上显著提升至O(log n),空间复杂度保持为O(1);动态规划通过牺牲O(n)空间换取O(n)时间内的高效计算。实际应用中,需根据具体需求权衡,如实时数据处理重视时间效率,而嵌入式系统更关注空间节约。通过不断优化,我们能在Python中找到最佳平衡点,实现高性能程序。
72 3
|
2月前
|
算法 C语言
深入理解算法效率:时间复杂度与空间复杂度
深入理解算法效率:时间复杂度与空间复杂度
|
7天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。