首页 > 编程语言 >算法设计与分析第一章

算法设计与分析第一章

时间:2022-12-15 23:22:58浏览次数:48  
标签:复杂度 Hard 第一章 问题 n0 算法 NP 设计

1、代码规范   代码缩进:左端对齐。   变量命名:首先变量命名要符合语法,在命名符合语法规范后可以采用驼峰命名法。即第一个单词以小写字母开始;从第二个单词开始以后的每个单词的首字母都采用大写字母。例如:myFirstName,myLastName之类的。   适当的注释:尤其是自己实现的功能一定要写好注释,方便别人调用。   2、算法与程序   2.1算法的4个特征:有穷性、确定性、输入、输出。   2.2程序是算法用某种程序设计语言的具体实现,可以不满足算法的有穷性。   3.算法的复杂性   算法的复杂性是算法效率的度量,是评价算法优劣的重要依据。一个算法的复杂性的高低体现在该算法所需要的时间资源和空间资源的多少上。   3.1空间复杂度:程序的空间复杂度指该程序运行时所需的内存空间的大小,包括指令空间、数据空间和函数调用。   3.2时间复杂度:算法的时间复杂度取决于求解问题的规模、具体的输入数据以及算法本身的设计。为了简化复杂度的分析,当问题规模n很大时,关注时间复杂度增长的阶,忽略时间复杂度中的低阶项和最高项的系数。   上界(O):设函数f(n)和g(n)是定义在非负整数集合上的正函数,如果存在两个正常数c和n0,使得当n≥n0时,有f(n)≤cg(n),则记做f(n) = O(g(n)),称为大O记号(big Oh notation) 称g(n)是f(n)的一个上界 。注:f(n)的阶不高于g(n)。   下界(Ω):设有函数f(n)和g(n)是定义在非负整数集合上的正函数,如果存在两个正常数 c和n0,使得当n≥n0时,有f(n)≥c g(n),则记做f(n) = Ω (g(n)),称为Ω记号(omega notation)。 注: f(n)的阶不低于g(n)。   渐进紧确界(θ):设有函数f(n)和g(n)是定义在非负整数集合上的正函数,如果存在正常数c1,c2和n0,使得当n≥n0时,有c1 g(n)≤f(n)≤c2 g(n),则记做f(n) = θ(g(n)),称为θ记号(Theta notation)。 注:此时f(n)和g(n)同阶。   3.3算法复杂度分类:     多项式复杂度:O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3)     指数复杂度:O(2n) < O(n!) < O(nn)  

 4.NP完全性理论

 

  4.1P类问题:存在多项式时间算法的问题。

 

  4.2NP问题:能在多项式时间内验证得出一个正确解的问题。

 

  4.3NPC类问题:存在这样一个NP问题,所有的NP问题都可以约化成它。

 

  4.4NP-Hard问题:NP-Hard问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard问题要比 NPC问题的范围广,NP-Hard问题没有限定属于NP),即所有的NP问题都能约化到它,但是它不一定是一个NP问题。

 

   

 

 

标签:复杂度,Hard,第一章,问题,n0,算法,NP,设计
From: https://www.cnblogs.com/Kimchow/p/16983871.html

相关文章

  • 寡人的难题 - 2021算法与数据结构实验题
    算法与数据结构实验题10.23寡人的难题题目内容★实验任务寡人心系天下为国为民,想要在历史中留下点痕迹,就必须要让国家强盛起来,正所谓想致富先修路,寡人觉得去修路,那些......
  • 一个开源的个人学习计算机科学知识成长记录(前后端,数据结构与算法)
    菜鸟进阶​​一个适合自学与巩固的学习记录​​​​前端项目积累​​​​前端入门​​​​HTML​​​​CSS​​​​JavaScript​​​​Browser​​​​Node​​​​DOM​​......
  • 程序设计模式急救笔记
    打完游戏发现考试内容一点没看,紧急抢救,精神状态不甚正常,慎读。例子有的不是很好,为了考试的时候抄个UML图方便罢了。0.UML图1.关联关系类A用到了类B,A->B类A用到了类B......
  • 算法第一章章末总结
    算法的第一章是算法概述,在本章节中,我们跟随老师的脚步一步步理解了算法的概念,掌握了评判算法好坏的标准,知道了算法在最坏情况、最好情况和平均情况下的计算复杂度概念,掌握......
  • 算法Blog
    ——编码规范1.不使用难懂的技巧性很高的语句,除非很有必要时高技巧语句不等于高效率的程序,实际上程序的效率关键在于算法。这可能是很多初学者最容易犯得错误。2.去掉......
  • 架构设计(三):引入缓存
    架构设计(三):引入缓存作者:Grey原文地址:博客园:架构设计(三):引入缓存CSDN:架构设计(三):引入缓存缓存是一个临时存储区域,如果请求的数据获取代价比较高或者数据的访问频率比较高......
  • 分智慧果 - 2021算法与数据结构实验题
    算法与数据结构实验题8.19分智慧果题目内容★实验任务老师准备把一筐智慧果分给班上的同学,第i个同学(从1开始编号)分到\(a_i\)个智慧果。Bonez(编号为1)是个自私的......
  • 模型驱动设计的构造块(上)——DDD
    为了保证软件实践得简洁并且与模型保持一致,不管实际情况如何复杂,必须运用建模和设计的实践。某些设计决策能够使模型和程序紧密结合在一起,互相促进对方的效用。这......
  • T-SQL语言基础 - 第一章笔记
    sql逻辑顺序1. FROM 指定要查询的表名,以及对这些表进行操作的表运算符2.WHERE指定一个谓词或逻辑表达式,从而过滤由FROM阶段返回的行。对查询性能有重要的影响,在......
  • 5分钟了解系统架构设计(2)
    最近梳理了之前学习的架构设计相关的一些课程学习总结,将其整理成了一个大纲脑图,以每篇5分钟系列展现出来,希望对你有所帮助。本篇,我们聚焦架构设计的理解部分。我们会从本......