首页 > 编程语言 >《计算机算法设计与分析》笔记

《计算机算法设计与分析》笔记

时间:2024-09-10 22:50:52浏览次数:13  
标签:问题 计算机 递归 int 笔记 char 算法 N0

第一章 算法概述

1.1算法性质:

输入、输出、确定性、有限性

1.2时间复杂度

  1. 上界记号O:如果存在正的常数C和自然数N0,使得当N≧N0时有f(N)≦Cg(N),则f(N)有上界函数g(N),记为f(N)= O(g(N))。

  2. 同阶记号θ:f(N)=θ(g(N))表示f(N)和g(N)同阶 。

  3. 下界记号Ω:如果存在正的常数C和自然数N0,使得当N≧N0 时有f(N)≧Cg(N),则f(N)有下界函数g(N),记为f(N) = Ω(g(N))。

1.3NP完全性理论

P类问题:是指一类能够用确定性算法在多项式时间内求解的判定问题。其实,在非正式的定义中,我们可以把那些在多项式时间内求解的问题当作P类问题。

NP类问题:是指一类可以用不确定性多项式算法求解的判定问题。(不确定性算法:非确定(“猜想”)阶段+确定(“验证”)阶段)

第二章 递归与分治策略 

2.1 递归

递归算法是一个直接或间接地调用自己的算法。

例1:阶乘函数

int  fac(int n)
{ if (n==0) return 1;
  return n*fac(n-1);
}

 例2:Hanoi塔问题。

汉诺塔问题可以通过以下三个步骤实现:

(1)将塔A上的n-1个碟子借助塔C先移到塔B上。

(2)把塔A上剩下的一个碟子移到塔C上。

(3)将n-1个碟子从塔B借助塔A移到塔C上。  

void move(char x,char y)
{
    printf("%c->%c\n",x,y);
}

void hanoi(int n, char a, char b, char c){
    if (n == 1) move(a,c);
    else 
    {                                              
        hanoi(n-1, a, c, b); 
        move(a,c);                         
        hanoi(n-1, b, a, c);             
}

例3:多变元递归——整数划分问题

例:整数划分问题:将一个正整数n表示为一系列正整数之和,n = n1 + n2 +…+nk    其中n1≥n2≥…≥nk≥1, k≥1。

 例如 p(6) = 11 ,即整数6的划分数为11种:  

6, 5+1, 4+2, 4+1+1,  3+3, 3+2+1, 3+1+1+1,  2+2+2, 2+2+1+1, 2+1+1+1+1, 1+1+1+1+1+1

最简单情形:(1) q(n, 1)=1,q(1, m) =1 n, m≥1;

递归关系: (2) q(n, n) = 1 + q(n, n–1),n>1;

产生的新情况: (3) q(n, m) = q(n, m–1) + q(n–m, m),  n>m>1          

划分中不含m的情况  划分中含m的情况 (4) q(n, m) = q(n, n),  n<m。

例4:多步递归——Fibonacci数列 

 

2.2分治法

解型为T(n)=aT(n/b)+O(nd)的递归方程

设a>=1和b>1是常数,f(n)是一个函数,

T(n)是定义在非负整数集上的函数:T(n)=aT(n/b)+ O(nd) 。

例1:二分搜索技术

int BinarySearch(Type a[ ], const Type &x, int n)
{
     int left=0;int right=n-1;
     while (left <= right ){ 
        int middle = (left+right)/2;
        if (x == a[middle]) return middle;
        if (x < a[middle]) right = middle-1; 
        else left = middle+1;
        }
    return -1;
}

例2:大整数的乘法

标签:问题,计算机,递归,int,笔记,char,算法,N0
From: https://blog.csdn.net/2301_80386162/article/details/142071812

相关文章

  • 计算机毕设选题(计算机专业,上百选题,送开题)
    基于SpringBoot的在线拍卖系统图书个性化推荐系统的设计与实现SpringBoot网页时装购物系统SpringBoot学生心理咨询评估系统基于SpringBoot的网上订餐系统大学生租房平台的设计与实现SpringBoot房屋租赁系统月度员工绩效考核管理系统大学生入学审核系统的设计与实现基......
  • 计算机网络
    计算机网络总分100=期中20+期末50+实验20+平时10(期中考前三章,期末考后三章)第一章概述1.1互联网两个重要基本特点:连通性、共享连通性:上网用户交换各种信息共享:指资源共享,可以是信息共享、软件共享、硬件共享1.2网络把许多计算机连接在一起,互连网把许多网络通过......
  • Supervision:你的可复用计算机视觉工具箱!!
    推荐一个计算机视觉的工具箱,使用它你可以在你电脑上实现人体跟踪、分割、检测等一系列计算机视觉的场景。Supervision是由Roboflow精心打造的开源计算机视觉工具,已经在GitHub上赢得了超过16k颗星星,人气爆棚!如果你想在你电脑上实现如下AI功能,可以试试这个工具。你可......
  • LeetCode算法—双指针
    一:普通双指针1、题目1:两数求和-1(1)方法1:普通双指针思路:定义两个指针;第一个指针放在数组的首位;第二个指针放在下一个元素的位置;然后遍历这个;如果两个元素的和为目标值就返回对对应的下标和索引值!deffuc(nums,target):foriinrange(len(nums)):forjinrange(i......
  • 【05】纯血鸿蒙HarmonyOS NEXT星河版开发0基础学习笔记-条件渲染+if/switch判断与for/
     序言:本文详细介绍了ArkTs语言中的数组、if单双多分支判断、switch判读、while循环、for循环并给出相应的具体案例和实现代码,附有综合案例京东购物的加购。笔者也是跟着B站黑马的课程一步步学习,学习的过程中添加部分自己的想法整理为笔记分享出来,如有代码错误或笔误,欢迎指正......
  • 【06】纯血鸿蒙HarmonyOS NEXT星河版开发0基础学习笔记-综合案例·生肖抽奖卡具体实现
    序言:本文综合了前五次笔记的知识内容,完成了相对来说较为复杂的生肖抽奖卡案例,通过拆分和一步步的思路分析完成本案例,通过完成这次案例,笔者可以说是把前面的所有内容或多或少的都有所复习,特此分享给大家。笔者也是跟着B站黑马的课程一步步学习,学习的过程中添加部分自己的想法......
  • Linux网络——从《计算机网络》到网络编程
    文章目录从《计算机网络》到网络编程从计算机到计算机网络解决问题网络与计算机系统计算机网络的传输流程IP地址与MAC地址从《计算机网络》到网络编程科班的同学大多学过计算机网络,而非科班的同学也多多少少听说过一些计算机网络体系十分繁杂且精妙,这三四十年来计......
  • Unity碰撞入门笔记
    Collider和Collider碰撞条件layer间可碰撞。其中之一为刚体。碰撞函数进入碰撞:OnCollisionEnter(Collisioninfo)碰撞中:OnCollisionStay(Collisioninfo)碰撞离开:OnCollisionExit(Collisioninfo)trigger物体作为trigger将没有碰撞,作为触发器使用。(例如到达点位刷怪)进......
  • Chapter 14 计算机网络基本概述
    欢迎大家订阅【Vue2+Vue3】入门到实践专栏,开启你的Vue学习之旅!文章目录前言一、网络的基本概念二、集线器、交换机和路由器三、互连网与互联网四、网络的类型五、互连网的组成1.边缘部分2.核心部分六、网络协议前言计算机网络是现代信息社会的基础,本章详细......
  • 计算机知识科普问答--5 (21-25)
    21、程序一定是算法吗?不是程序和算法的区别算法(Algorithm):解决问题的一组明确、有序的步骤或规则。特性:有穷性、确定性、可行性。程序(Program):用编程语言编写的一组指令,包含算法的实现和其他功能。特性:执行性、完整性。程序不一定是算法,但程序可以包含一个......