算法与数据结构(一)--算法复杂性

这篇具有很好参考价值的文章主要介绍了算法与数据结构(一)--算法复杂性。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法--解决问题的方法
数据结构--数据之间的逻辑关系

一.算法复杂性的概念

算法的复杂性是指运行算法所需要的计算机资源的量。需要的时间资源的量称为时间复杂性,需要的空间资源的量称为空间复杂性。
这个量应该集中反映算法的效率,而从运行该算法的实际计算机中抽象出来。换句话说,这个量应该是只依赖与算法要解的问题的规模(n)算法的输入(l)的函数。
这样算法复杂性可以表示为C(n,I),其中n表示算法要解问题的规模和算法的输入,用C表示复杂性。同理时间复杂度可以表示为T=T(n,I)空间复杂度可以表示为S=S(n,I)
一般考虑复杂度的时候,我们会考虑最坏,最好,平均三种情况下的复杂度。

二.算法复杂性的渐进性态和时间复杂度的计算

【1】了解了算法复杂性,那么怎么计算呢? 以时间复杂度为例:

在这里,我们需要明确一个事情:执行次数=执行时间
按照上面的算法,第一个算法的时间复杂度就是1+1+(n+1)+n=2n+3次,第二个算法的时间复杂度就是1+1+1=3=次,但是这样算太麻烦了。
实际上我们只需要考虑核心代码的执行次数,并且我们只需要考虑当n足够大时就行了。

【2】下面是如何进行化简


(1)我们可以用T(n)的渐进表达式替代T(n)来进行复杂度分析的简化,直观上,这个渐进表达式就是T(n)中略去低阶项所留下的主项(其实就是最高项),所以它比T(n)更简单。比如:算法与数据结构(一)--算法复杂性,数据结构=>
(2)当两个算法的阶不相同时候,渐近复杂性分析只要关心T(n)的渐进表达式的阶就够了不必关心包含在该渐进表达式中的常数因子。因此又可对该渐进表达式的分析进一步简化,即假设算法中用到的所有不同的元运算各执行一次所需要的时间都是一个单位时间。比如:
=>


总而言之我们分析的时候,只需要考察当问题的规模充分大时,算法的复杂性在渐进意义下的阶。

简单说就是只要计算当n足够大时的阶就够了,而不用去管常数和低阶项。

回到刚开始那道题,不难得出第一个算法的算法复杂度可以简化为n,我们记为O(n),第二个算法的算法复杂度可以简化为1,我们记为O(1)。那么再来看看下面这段代码并计算时间复杂度:

#include <stdio.h>
double Cab(double a,double b){
	double fm=1;
	double fz=1;
	for(double i=0;i<b;i++)
		fm=fm*(a-i);
	for(double i=2;i<=b;i++)
		fz=fz*i;
	return fm/fz;
}
int main(){
    int N;
    scanf("%d",&N);
    int max2=N/2;
    double countType=1;
    for(int i=1;i<=max2;i++){
    	countType=Cab(N-i,i)+countType;
	}
	printf("%.0lf",countType);
    return 0;
}

先忽略前面输入的代码,只注重核心代码。外层循环是2/n,但是我们当成n即可,内层循环约2b,而b又可以看成和n有关的一次变量,所以内层循环也当成n,所以这个爬楼梯算法的时间复杂度就是O(n^2),而用斐波那契数列进行简化可以达到O(n)。

附录:
O(n)的定义,例子与运算规则:
算法与数据结构(一)--算法复杂性,数据结构

(1) 根据符号O的定义,得到的只是当规模充分大时的上界。【就像上面的可以等于O(),也可以等于O()等等】这个上界的阶越低,评估就越精确。

(2)除了O外,还有,得到的只是该复杂性的下界。这个下界的阶月高,评估就越精确。具体定义这里懒得写了。
(3)还有符号。定义f(n)=(g(n))当且仅当f(n)=O(g(n))且f(n)=(g(n)),这时认为f(n)与g(n)同阶

下面是常见的算法复杂度:

算法与数据结构(一)--算法复杂性,数据结构

【3】最坏情况

例:有一个存储了n个随机数字的数组,请从中查找出指定的数字。

public int search(int num){
    int[] arr={11,10,8,9,7,22,23,0};
    for (int i = 0; i < arr.length; i++) {
        if(num==arr[i]){
            return i;
        }
    }
    return -1;
}

最好情况:
查找的第一个数字就是期望的数字,那么算法的时间复杂度为O(1)
最坏情况:
查找的最后一个数字,才是期望的数字,那么算法的时间复杂度为O(n)
平均情况:
任何数字查找的平均成本是O(n/2)
最坏情况是一种保证,在应用中,这是一种最基本的保障,即使在最坏情况下,也能够正常提供服务,所以,除非特别指定,我们提到的运行时间都指的是最坏情况下的运行时间。

三.空间复杂度

【1】java中常见内存占用

算法与数据结构(一)--算法复杂性,数据结构

算法与数据结构(一)--算法复杂性,数据结构

【2】空间复杂度的计算

案例:对指定的数组元素进行反转,并返回反转的内容
解法一:

public static int[] reverse1(int[] arr){
    int n=arr.length;//申请4个字节
    int temp;//申请4个字节
    for(int start=0,end=n-1;start<=end;start++,end--){
        temp=arr[start];
        arr[start]=arr[end];
        arr[end]=temp;
    }
    return arr;
}

解法二:

public static int[] reverse2(int[] arr){
    int n=arr.length;//申请4个字节
    int[] temp=new int[n];//申请n*4个字节+数组自身头信息开销24个字节
    for (int i = n-1; i >=0; i--) {
        temp[n-1-i]=arr[i];
    }
    return temp;
}

算法一: 不管传入的数组大小为多少,始终额外申请4+4=8个字节;
算法二: 4+4n+24=4n+28;
根据化简,算法一的空间复杂度为O(1),算法二的空间复杂度为O(n),所以从空间占用的角度讲,算法一要 优于算法二。
由于java中有内存垃圾回收机制,并且jvm对程序的内存占用也有优化(例如即时编译),我们无法精确的评估一 个java程序的内存占用情况,但是了解了java的基本内存占用,使我们可以对java程序的内存占用情况进行估算。
由于现在的计算机设备内存一般都比较大,基本上个人计算机都是4G起步,大的可以达到32G,所以内存占用一般 情况下并不是我们算法的瓶颈,普通情况下直接说复杂度,默认为算法的时间复杂度。
但是,如果你做的程序是嵌入式开发,尤其是一些传感器设备上的内置程序,由于这些设备的内存很小,一般为几 kb,这个时候对算法的空间复杂度就有要求了,但是一般做java开发的,基本上都是服务器开发,一般不存在这样 的问题。文章来源地址https://www.toymoban.com/news/detail-535411.html

到了这里,关于算法与数据结构(一)--算法复杂性的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 策略复杂性增加,管理困难和维护困难,影响安全和性能

    本文将探讨防火墙策略管理的挑战与问题,以及针对这些问题提出的解决方案。首先,我们将讨论策略复杂性的增加及其带来的负面影响,包括管理困难、维护困难和安全风险等;然后,我们提出相应的解决方案以解决这些挑战和问题。 防火墙是网络安全的关键组件,它们可

    2024年02月04日
    浏览(36)
  • 策略复杂性增加,难以理解和维护,影响安全效果和性能表现

    随着互联网技术的迅速发展,网络攻击日益猖獗。为了提高网络安全效果和性能表现,我们需要更加深入地了解和管理防火墙策略。本文将围绕以下三个问题进行分析和提出解决方案: 问题一:策略复杂性增加 随着网络攻击的复杂程度不断提高,防火墙需要处理的攻击类型

    2024年02月03日
    浏览(33)
  • (MIT6.045)自动机、可计算性和复杂性-图灵机

    有穷自动机(FA)对有限存储量设备是比较好的模型,下推自动机对无限存储设备是较好的模型(但是其存储只能用后进先出的栈模式来使用。)这两个模型过于局限,不能作为通用模型。 和FA相似,但是图灵机有无限的存储。图灵机可以作实际计算机做的所有事情。但是也有图

    2024年02月08日
    浏览(39)
  • 算法的复杂度【数据结构】

    算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源,因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的,即 时间复杂度 和 空间复杂度 时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。 方法

    2024年02月08日
    浏览(40)
  • 【数据结构】算法的复杂度

    大家好!今天我们来学习算法的复杂度。 目录 1. 前言 1.1 什么是数据结构? 1.2 什么是算法? 2. 算法效率 3. 时间复杂度 3.1 时间复杂度的概念 3.2 大O的渐进表示法 3.3 常见时间复杂度计算举例 ​4. 空间复杂度 4.1 空间复杂度的概念 4.2 常见空间复杂度计算举例 5. 常见复杂度

    2024年02月11日
    浏览(39)
  • 数据结构:算法(特性,时间复杂度,空间复杂度)

    算法(Algorithm)是对 特定问题求解步骤 的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。 一个算法必须总在执行有穷步之后结束,且每一步都可在有穷时间内完成。 算法必须是有穷的,而程序可以是无穷的 算法中每条指令必须有确切的含义,对于

    2024年02月06日
    浏览(57)
  • 数据结构与算法复杂度介绍

    目录 一、基本概念 二、时间复杂度 【2.1】时间复杂度概念 【2.2】大O的渐进表示法 【2.3】举例时间复杂度计算 三、空间复杂度 数据结构 :相互之间存在一种或者多种特定关系的数据元素的集合。在逻辑上可以分为线性结构,散列结构、树形结构,图形结构等等。 算法 :

    2024年02月10日
    浏览(38)
  • 数据结构与算法之复杂度

    时间复杂度 1.抓大头 2.常数用o(1),低阶函数也用o(1)代替(直接去掉) 3.取最坏情况 对数相关写法的规定

    2024年02月07日
    浏览(19)
  • 算法与数据结构-复杂度分析

      算法的执行效率,粗略地讲,就是算法代码执行的时间。但是,如何在不运行代码的情况下,用“肉眼”得到一段代码的执行时间呢?   这里有段非常简单的代码,求 1,2,3…n 的累加和。现在,我就带你一块来估算一下这段代码的执行时间。   从 CPU 的角度来看,这

    2024年02月08日
    浏览(55)
  • 算法之时间复杂度---数据结构

    目录 前言: 1.时间复杂度 1.1时间复杂度的理解 1.2规模与基本操作执行次数 1.3大O渐进表示法 1.4计算基本操作的次数 2.常见的时间复杂度及其优劣比较 ❤博主CSDN:啊苏要学习     ▶专栏分类:数据结构◀   学习数据结构是一件有趣的事情,希望读者能在我的博文切实感受到

    2024年02月05日
    浏览(68)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包