精华内容
下载资源
问答
  • 2017-06-16 17:06:20

    它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    package com;
    
    public class maopao {
    
        public int kuaipai(int l,int r,int a[])
        {
            //将区间最左边的作为基准数
            int key=a[l];
            while(l<r)
            {
                while(l<r && key <= a[r])
                    r--;
                a[l]=a[r];
                while(l<r && key >= a[l])
                    l++;
                a[r]=a[l];  
            }
            a[l]=key;
            return l;
        }
        public static void main(String[] args) {
            int a[]={4,2,9,3,5,7,9,0};
            maopao m=new maopao();
            //返回基准数所在的位置
            int mid=m.kuaipai(0,a.length-1,a);
            m.kuaipai(0, mid-1, a);
            m.kuaipai(mid+1, a.length-1, a);
            for(int i = 0;i <= a.length-1; i++)
                System.out.print(a[i]);
        }
    }
    
    • 1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
    • 2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];
    • 3)从j开始向前搜索,即由后开始向前搜索(j–),找到第一个小于key的值A[j],将A[j]和A[i]互换;
    • 4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
    • 5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。

    快速排序最优时间复杂度:O(nlog2n)

    最快的时间复杂度是 :O(nlog2n)

    最差的时间复杂度:O(n^2)

    更多相关内容
  • 适用于ISO / IEC / IEEE21451-5传感器和执行器网络的低复杂度错误校正
  • 适用于ISO / IEC / IEEE 21451-5传感器和执行器网络的低复杂度错误校正
  • 复杂度及降低示例

    2021-08-06 09:01:58
    复杂度复杂度定义计算规则降低圈复杂度手段降低圈复杂度示例修改 圈复杂度 定义 圈复杂度 (Cyclomatic complexity) 是一种代码复杂度的衡量标准,也称为条件复杂度或循环复杂度,它可以用来衡量一个模块判定结构...

    圈复杂度

    定义

    圈复杂度 (Cyclomatic complexity) 是一种代码复杂度的衡量标准,也称为条件复杂度或循环复杂度,它可以用来衡量一个模块判定结构的复杂程度,数量上表现为独立现行路径条数,也可理解为覆盖所有的可能情况最少使用的测试用例数。简称 CC 。其符号为 VG 或是 M 。

    计算规则

    for +1; if +1; else +1; switch has n cases +n; || +1; && +1

    降低圈复杂度手段

    1、类型判断、转换

    if (visibleFlag) {
        visible = 1;
    } else {
        visible = 0;
    }
    改为(如:在数据库保存时无法自动转换数据类型):
    visible = visibleFlag + 0
    

    2、独立函数调用

    postTitle = postTitle ? postTitle.trim() : '';
    改为:
    postTitle = util.trim(xss.sanitize(postTitle))
    

    3、多条件合并为一个:转为数组的include等操作

    if (action === 'create' || action === 'edit') {...}
    改为:
    if (['create', 'edit'].includes(action)) {...}
    

    4、空值判断简化

    if (page !== undefined && page !== ''){...}
    改为
    if (!page) {...}
    

    5、嵌套if简化

    if (x) {
        if (y) {...} else {...}
    } else {
        ...
    }
    改为:
    if (x && y) {...} else {...}
    

    6、复杂if改为使用正则(通配符)

    if (/^1[34578]\d{9}$/i.test(phone)) {...}
    

    7、重复判断剥离并复用:赋值给变量、常量,减少二次判断

    if (postStatus === 'draft' || postStatus === 'auto-draft') {...}
    ...
    if (postStatus === 'draft' || postStatus === 'auto-draft') {...} else {...}
    改为:
    const postDraft = postStatus === 'draft' || postStatus === 'auto-draft';
    if (postDraft) {...}
    

    降低圈复杂度示例

    阈值5。下面这种if判空后赋值有九处(4+5),加上两个err判断,使得原代码圈复杂度为12

    func (p *Pipe) getVersionDetails(ctx *context.Context, app *asc.App, version *asc.AppStoreVersion) error {
      // *asc.AppInfoLocalizationResponse error  类型
    	appLocalizationResp, err := p.Client.GetAppLocalizations(ctx, app.ID)
    	if err != nil {
    		return err
    	}
      // Name Subtitle ... 是*string类型
    	if appLocalizationResp.Data.Attributes.Name != nil {
        // AppStoreVersionDetail是model.MarketReleaseIosReq类型
    		ctx.AppStoreVersionDetail.App = *appLocalizationResp.Data.Attributes.Name
    		log.Info("ctx.AppStoreVersionDetail.App:", ctx.AppStoreVersionDetail.App)
    	}
    	if appLocalizationResp.Data.Attributes.Subtitle != nil {
    		ctx.AppStoreVersionDetail.SubTitle = *appLocalizationResp.Data.Attributes.Subtitle
    		log.Info("ctx.AppStoreVersionDetail.Subtitle:", ctx.AppStoreVersionDetail.SubTitle)
    	}
      ...
      ...
    
    	return nil
    }
    

    修改

    func (p *Pipe) getVersionDetails(ctx *context.Context, app *asc.App, version *asc.AppStoreVersion) error {
    
    	log.Infof("getting app localizations")
    	appLocalizationResp, err := p.Client.GetAppLocalizations(ctx, app.ID)
    	if err != nil {
    		return err
    	}
    	InitAppVersionDetailAppInfo(ctx, appLocalizationResp)
    
    	...
    
    	return nil
    }
    
    // InitAppVersionDetailAppInfo 初始化ctx.AppStoreVersionDetail
    func InitAppVersionDetailAppInfo(ctx *context.Context,
    	appLocalizationResp *asc.AppInfoLocalizationResponse) {
    	InitProp(ctx.AppStoreVersionDetail, "App", appLocalizationResp.Data.Attributes.Name)
    	InitProp(ctx.AppStoreVersionDetail, "PrivacyPolicyURL", appLocalizationResp.Data.Attributes.PrivacyPolicyURL)
    	InitProp(ctx.AppStoreVersionDetail, "Subtitle", appLocalizationResp.Data.Attributes.Subtitle)
    	InitProp(ctx.AppStoreVersionDetail, "PrivacyPolicyText", appLocalizationResp.Data.Attributes.PrivacyPolicyText)
    }
    // 赋值功能核心
    // 结构体是值类型,用指针类型才会改变值。不用指针是传对象的副本,在函数外访问是没变化的。
    func InitProp(appStoreVersionDetail *model.MarketReleaseIosReq,
    	ctxPropertyName string, respAttribute *string) {
    	if respAttribute == nil {
    		return
    	}
    	detail := reflect.Indirect(reflect.ValueOf(&appStoreVersionDetail)).Elem()
    	typeOfT := detail.Type()
    	for i := 0; i < detail.NumField(); i++ {
    		if typeOfT.Field(i).Name == ctxPropertyName {
    			detail.FieldByName(ctxPropertyName).Set(reflect.ValueOf(respAttribute).Elem())
    			break
    		}
    	}
    	log.Infof("ctx.AppStoreVersionDetail.%+v:%+v", ctxPropertyName, reflect.ValueOf(respAttribute).Elem())
    }
    
    展开全文
  • 计算有限域GF(q)上2pn-周期序列的k-错 线性复杂度及其错误序列的算法
  • (unix中)oracle修改用户密码复杂度的具体例子及操作过程,本例子是为企业做oracle数据库安全时的实际操作过程,包括密码长度,要求字符类型,过期时间,提示过期时间,密码错误次数等等!
  • 实验结果表明,在许多基准数据集上,所提出的方法学习的分类器的错误率远低于传统的 SVM,同时通常使用更少的支持向量。 在许多基准数据集上,支持向量的数量不到 SVM 使用的数量的十分之一,表明 MCM 确实学习了更...
  • 就空间复杂度来说,主要是递归造成的栈空间的使用,最好情况,递归树的深度为log2n,其空间复杂度也就为O(logn),最坏情况,需要进行n‐1递归调用,其空间复杂度为O(n),平均情况,空间复杂度也为O(logn)。...

    我们来分析一下快速排序法的性能。快速排序的时间性能取决于快速排序递归的深度,可以用递归树来描述递归算法的执行情况。如图9‐9‐7所示,它是{50,10,90,30, 70,40,80,60,20}在快速排序过程中的递归过程。由于我们的第一个关键字是50,正好是待排序的序列的中间值,因此递归树是平衡的,此时性能也比较好。

     
    图9-9-7
    在最优情况下,Partition每次都划分得很均匀,如果排序n个关键字,其递归树的深度就为.log2n.+1(.x.表示不大于x的最大整数),即仅需递归log2n次,需要时间为T(n)的话,第一次Partiation应该是需要对整个数组扫描一遍,做n次比较。然后,获得的枢轴将数组一分为二,那么各自还需要T(n/2)的时间(注意是最好情况,所以平分两半)。于是不断地划分下去,我们就有了下面的不等式推断。
     
    1. T(n)≤2T(n/2) +n,T(1)=0  
    2. T(n)≤2(2T(n/4)+n/2) +n=4T(n/4)+2n  
    3. T(n)≤4(2T(n/8)+n/4) +2n=8T(n/8)+3n  
    4. ……  
    5. T(n)≤nT(1)+(log2n)×nO(nlogn) 

    也就是说,在最优的情况下,快速排序算法的时间复杂度为O(nlogn)。

    在最坏的情况下,待排序的序列为正序或者逆序,每次划分只得到一个比上一次划分少一个记录的子序列,注意另一个为空。如果递归树画出来,它就是一棵斜树。此时需要执行n‐1次递归调用,且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录,也就是枢轴的位置,因此比较次数为 ,最终其时间复杂度为O(n2)。

    平均的情况,设枢轴的关键字应该在第k的位置(1≤k≤n),那么:

     

    由数学归纳法可证明,其数量级为O(nlogn)。

    就空间复杂度来说,主要是递归造成的栈空间的使用,最好情况,递归树的深度为log2n,其空间复杂度也就为O(logn),最坏情况,需要进行n‐1递归调用,其空间复杂度为O(n),平均情况,空间复杂度也为O(logn)。

    可惜的是,由于关键字的比较和交换是跳跃进行的,因此,快速排序是一种不稳定的排序方法。


    来源:http://blog.csdn.net/weshjiness/article/details/8660583

    展开全文
  • 时间复杂度与空间复杂度1.算法的复杂度:2.时间复杂度:1.大O表示法:2.大O推导方法:3.一些常见的大O运行时间:3.空间复杂度:4.个别特殊举例:1.斐波那契数列的时间和空间复杂度2.二分法的时间复杂度和空间复杂度 ...

    1.算法的复杂度:

    算法的时间复杂度和空间复杂度合称为算法的复杂度。

    时间复杂度: 时间复杂度是指执行算法所需要的计算工作量;

    空间复杂度: 是对一个算法在运行过程中临时占用存储空间大小的量度;

    算法的复杂性体运行该算法时的计算机所需资源的多少上,计算机资源最重要的是时间和空间(即寄存器)资源,因此复杂度分为时间和空间复杂度。

    2.时间复杂度:

    一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度,记为T(n)。

    一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f (n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
    在这里插入图片描述

    1.大O表示法:

    用O( )来体现算法时间复杂度的记法,我们称之为大O表示法。

    算法复杂度可以从最理想情况、平均情况和最坏情况三个角度来评估,由于平均情况大多和最坏情况持平,而且评估最坏情况也可以避免后顾之忧,因此一般情况下,我们设计算法时都要直接估算最坏情况的复杂度。大O表示法所表示的是一个算法在最糟糕情况下的运行时间。

    2.大O推导方法:

    1.用常数1来取代运行时间中所有加法常数。

    2.修改后的运行次数函数中,只保留最高阶项

    3.最高项除去其相乘的常数,得到的结果就是大O阶。

    举例:

    单个循环体情况:

    void Demo(int n){
    		for(int j = 0; j < n; j++) {        // 循环次数为 n
                printf("Hello, World!\n");      // 循环体时间复杂度为 O(1)
            }
    }
    //时间复杂度为 O(n × 1),即 O(n)。
    

    多重循环体情况:

    void Demo(int n) {
    for(int i = 0; i < n; i++) {            // 循环次数为 n
            for(int j = 0; j < n; j++) {        // 循环次数为 n
                printf("Hello, World!\n");      // 循环体时间复杂度为 O(1)
            }
        }
    }   
    //时间复杂度为 O(n × n × 1),即 O(n^2)。
    

    多个事件复杂度情况:

    void Demo(int n) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                printf("Hello, World!\n");// 第一部分时间复杂度为 O(n^2)
            }
        }
        for(int j = 0; j < n; j++) {
            printf("Hello, World!\n");// 第二部分时间复杂度为 O(n)
        }
    }
    //时间复杂度为 max(O(n^2),O(n)),即 O(n^2)。
    

    3.一些常见的大O运行时间:

    • O(log n),对数时间,二分查找。
    • O(n),线性时间,简单查找。
    • O(n logn),快速排序——速度较快的排序算法。
    • O(n²),选择排序——速度较慢的排序算法。
    • O(n!),旅行商问题的解决方案——非常慢的算法。

    3.空间复杂度:

    一个程序的空间复杂度是指运行完一个程序所需内存的大小,利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。

    (1)固定部分:这部分空间的大小与输入/输出的数据的个数多少、数值无关,主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间,这部分属于静态空间。

    (2)可变空间:这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等,这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)),其中n为问题的规模,S(n)表示空间复杂度。

    通常来说,只要算法不涉及到动态分配的空间以及递归、栈所需的空间,空间复杂度通常为0(1)。

    4.个别特殊举例:

    1.斐波那契数列的时间和空间复杂度

    //递归情况下的斐波那契数列
        public static int Fib(int num){
            if (num==1||num==2){
                return num;
            }
            return Fib(num-2)+Fib(num-1);
        }
    

    递归的时间复杂度是: 递归次数*每次递归中执行基本操作的次数,所以,时间复杂度是: O(2^N)。

    递归的空间复杂度是: 递归的深度*每次递归所需的辅助空间的个数,所以,空间复杂度是:O(N)。

    2.二分法的时间复杂度和空间复杂度

    二分查找在最坏的情况下依次是n/2,n/4,n/8一直到1为止。
    假设是x次,然后我们可以观察到分母是每次都乘以1/2,分子不变,所以可以列出下面等式:

    n(1/2)^x = 1

    通过计算得出x=log2N,即时间复杂度为O(log2N);

    非递归:

    public static int binarySearch(int[] arr,int toFind) {
            int left = 0;
            int right = arr.length-1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (arr[mid] < toFind) {
                    left = mid + 1;
                }
                else if (arr[mid] > toFind) {
                    right = mid - 1;
                }
                else {
                    return mid;
                }
            }
            return -1;
        }
    

    时间复杂度:循环的基本次数是log2N,所以,时间复杂度是O(log2N);

    空间复杂度:由于辅助空间是常数级别的,所以,空间复杂度是O(1)。

    递归:

    public static int binarySearch(int srcArray[], int start, int end, int key) {
            int mid = (end - start) / 2 + start;
            if (srcArray[mid] == key) {
                return mid;
            }
            if (start >= end) {
                return -1;
            } else if (key > srcArray[mid]) {
                return binarySearch(srcArray, mid + 1, end, key);
            } else if (key < srcArray[mid]) {
                return binarySearch(srcArray, start, mid - 1, key);
            }
            return -1;
        }
    

    递归的次数和深度都是log2N,每次所需要的辅助空间都是常数级别的:
    时间复杂度 : O(log2N)
    空间复杂度:O(log2N)

    展开全文
  • 详解圈复杂度

    2021-03-09 08:43:33
    详解圈复杂度复杂度概念圈复杂度(Cyclomatic complexity,简写CC)也称为条件复杂度,是一种代码复杂度的衡量标准。由托马斯·J·麦凯布(Thomas J. McCabe, Sr.)于1976年提出,用来表示程序的复杂度,其符号为VG...
  • 时间复杂度

    2021-04-28 02:24:47
    在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,...
  • 快速入门时间复杂度&空间复杂度

    多人点赞 热门讨论 2022-01-26 14:02:40
    时间复杂度与空间复杂度快速入门
  • ⭐前言⭐复杂度时间复杂度概念的引出实战分析线性常数阶平方阶二分查找对数阶及证明递归线性指数爆炸空间复杂度概念的引出实战分析循环重复创建变量递归线性????结尾语???? ⭐前言⭐ 本文将要介绍数据结构的开篇–...
  • 什么是圈复杂度?

    2022-06-13 14:37:31
    复杂度是衡量软件质量的一个重要指标。 在这里,我们将阐释什么是圈复杂度和圈复杂度McCabe,并提供圈复杂度的示例。
  • 算法复杂度分为时间复杂度和空间复杂度。其作用:时间复杂度是指执行这个算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。时间和空间(即寄存器)都是计算机资源的重要体现,而算法的复杂性...
  • 时间复杂度为O(nlogn) n为元素个数 1. 快速排序的三个步骤: 1.1. 找到序列中用于划分序列的元素 1.2. 用元素划分序列 1.3. 对划分后的两个序列重复1,2两个步骤指导序列无法再划分 所以对于n个元素其排序时间为 T...
  • 软件复杂度和圈复杂度

    千次阅读 2018-12-24 15:30:19
    软件复杂度和圈复杂度 软件复杂度 1,起源与应用 成立于1976的McCabe &amp;amp; Associates公司开发出了McCabe Cyclomatic Complexity Metric(McCabe圈复杂度)技术对软件进行结构测试。 McCabe复杂度是...
  • 时间复杂度入门理解

    2021-01-14 05:56:19
    因此,对于模块化程序,优化其算法的时间复杂度是非常重要的。定义我们把一个算法中的语句执行次数定义为频度,算法的运行时间刻画为一个函数,定义为 T(n) ,其中n称为问题的规模,当n不断变化时,T(n)也随之变化。...
  • 该模型降低了立体视频左、右视点帧之间的依赖性,具有较低的复杂度。实验表明,对于不同的丢包率和缓慢运动的立体视频序列,该模型均能准确估计视点内和视点间错误扩散,进而快速估计出终端立体视频传输失真。
  • 针对广义割圆序列的构造问题,提出周期为pm的任意阶广义割圆序列的构造方法,...结果表明,该序列具有较好的线性复杂度,能抗击B-M算法,可用于推广现有的周期为pm序列的相关研究,并对已有文献中的部分错误证明进行订正。
  • 时间复杂度和空间复杂度是什么? 时间复杂度是一个算法运行所需要的时间。空间复杂度是一个算法运行所需要的储存空间。它们常常被人们用来检测一个算法的质量好坏。在实际操作中,这两个指标往往无法同时兼顾,都...
  • 算法复杂度分析

    2021-12-12 03:53:15
    复杂度分析就是算法世界基本的是非观,只有掌握了复杂度分析,我们才能对代码的效率好坏有一个基本的判断能力。如果你只是掌握了数据结构和算法的特点、用法,但是没有学会复杂度分析,那就相当于学武功只学习了招式...
  • 文章目录算法时间复杂度推导大O阶方法常数阶线性阶对数阶 算法时间复杂度 定义:在进行算法分析时,语句总的执行次数T(n)是关于问题模型n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,...
  • 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。 这个算法的名字由来是因为越大的元素会经由...
  • 复杂度计算

    千次阅读 2019-11-06 17:15:12
    计算公式1:V(G)=e-n+2p。其中, e表示控制流图中边的数量, n表示控制流图中节点的数量, p图的连接组件数目(图的组件数是相连节点的...所以圈复杂度实际上就是等于判定节点的数量再加上1,也即控制流图的区域数...
  • =i) System.out.println("***错误***"); } return System.currentTimeMillis()-start; } public static void main(String args[])...{ System.out.println("ArrayList消耗时间:"+timeList(new ArrayList(values)));...
  • 还在头疼时间复杂度如何计算?来看下本文,彻底学会时间复杂度问题的求解。
  • 江湖中,传闻,算法效率有时空之分,具体来说便是时间效率与空间效率之分: 时间效率被称为时间复杂度——衡量一个算法的运行速度 空间效率被称为空间复杂度——衡量一个算法所需的额外空间 在计算机发展早期,...
  • 一般认为k错线性复杂度低的序列是不稳定的,不适合作为密钥序列,但是有的序列只有在改变某些位置才会引起线性复杂度的下降,k位置错误谱描述了错误位置的不同对线性复杂度的影响。主要是研究周期为2n的二元序列,发现这...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 215,548
精华内容 86,219
关键字:

复杂度错误