算法导论笔记（1）_假设一个n个记录中每个的关键字都介于1到k之间。说明如何修改计数排序,使得可以在-程序员宅基地

技术标签： 算法  

#习题2.3-7 给定整数数组S和目标值x，是否存在S中的两个元素之和为x，要求时间复杂度为O(n*log n)。

解：对S中的每个元素a，二分查找 x - a。

#习题2-4 计算数组中的逆序对，时间复杂度O(n*log n)。 提示：归并排序。另外如果只允许交换相邻元素，通过最少的交换次数将数组排序，答案是选择排序或插入排序，因为一次交换最多消除一个逆序对，而选择排序和插入排序每次必然消灭一个逆序对。

#例4.1 股票买卖问题：知道n天的股价，选择某一天买入及此后的某天卖出，要求获益最大。

解：计算每一天与前一天的差价，转化为最大字数组和问题。

#习题4.1-5 线性时间求最大字数组

解：令max[j]为以A[j]结尾的最大字数组和，max[j+1]=max(0, max[j]+A[j+1], A[j+1])

#习题4.2-7 三次相乘计算复数乘法

解： (a+bi)(c+di) 令 x=(a-b)(c+d)  y=ad  z=bc 则实部为x-y+z，虚部为y+z

#习题5.3-5 从n^3个数字中进行放回抽样，共抽n次，证明n次抽到的数字全不相同的概率至少为 1- 1/n

证明：定义事件Xi为第i次抽到的数字以前抽到过，则P(Xi) <= (i-1)/n^3，故至少有两次相同的概率 <= P(X2)+P(X3)+...+P(Xn) < 1/n^3 + 2/n^3 + ... + (n-1)/n^3 < 1/n

#习题5.3-7 从n个数中随机取m个，证明如下方法是无偏的


证明：用数学归纳法，证明任意组合发生的概率为1/C(n,m)。首先第5行为真的概率为(m-1)/n。对于组合(a1, a2, ..., am)，分两种情况讨论。若am=n则 i=n或者第5行为真，故am=n的概率为1/n + (m-1)/n = m/n，而在第4行(a1, a2, ..., a_(m-1))发生的概率为1/C(n-1, m-1)，故(a1, a2, ..., am)的概率为 (m/n) * 1/C(n-1, m-1)  = C(n, m)。若am != n，设最后取到的数是i，则第4行的概率为1/n，故取到(a1, .., am)且最后一次是i的概率为 1/n * 1/C(n-1, m-1)，由于i可能是(a1, ..., am)中的任一个，故总概率为 m * 1/n * 1/C(n-1, m-1) = 1/C(n, m)。

#堆排序：从后向前建堆时间复杂度为O(n)，从前向后建堆为O(n log(n))

#二叉堆的叶子节点为ceiling(n/2)

证明：令d=叶子数量 - 内节点数量，则每增加一个左节点，叶子不变，内节点+1，故d减1；每增加一个右节点，d加1。从根节点开始(d=1)，就是一个 -1+1-1+1...的序列，d永远是0或1

#习题8.2-3 计数排序最后一步为什么要从后向前遍历？答：为了保证排序的稳定性。

#习题8-2 线性时间原地排序
假设有一个有n个数据记录组成的数组要排序，且每个记录的关键字的值为0或1。排序这样一组记录的一个算法应具备如下三个特性中的一部分。
1）算法的运行时间为O(n)。
2）算法是稳定的。
3）算法是原地排序的，它可以使用除输入数组以外的固定量的存储空间。

a）给出一个满足上述条件1和条件2的算法。(计数排序)
b）给出一个满足上述条件1和条件3的算法。(使用快速排序中的partition步)
c）给出一个满足上述条件2和条件3的算法。(插入排序)

e）假设一个n个记录中每个的关键字都介于1到k之间。说明如何修改计数排序，使得可以在O(n+k)时间内对n个记录原地排序。除输入数组外，可另用O(k)的存储空间。你给出算法是稳定的吗？（提示：当k=3时应该如何做）

解：在计数排序的最后一步，从前向后遍历（从后向前也可），将元素与该元素应该在的位置上的元素交换。不稳定。

static void countingSortInPlace(int[] a, int k) {
    int[] endidx = new int[k];
    for(int x : a) {
        endidx[x]++;
    }
    endidx[0] -=  1;
    for(int i=1; i<endidx.length; i++) {
        endidx[i] += endidx[i-1]; 
    }
    //endidx[x]为x的插入位置
    int i = 0;
    while(i < a.length) {
        int x = a[i];
        if(i >= endidx[x]) {
            i++; //x已全部归位
        } else {
            swap(a, i, endidx[x]);
            endidx[x] -= 1;
        }
    }
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/groovy2007/article/details/25821823

智能推荐

に的用法(转)-程序员宅基地

文章浏览阅读277次。&lt;script type="text/javascript"&gt;&lt;!--google_ad_client = "pub-0241434510974184";/* 博客文章广告728x90, */google_ad_slot = "7316585398";google_ad_width = 728;google_ad_height = 90;// --&g..._!jjjjnjuuhhuyyhhzhzhggdvbvhyz

Python异步IO之协程(二):使用asyncio的不同方法实现协程-程序员宅基地

文章浏览阅读3.6k次，点赞13次，收藏38次。引言：在上一章中我们介绍了从yield from的来源到async的使用，并在最后以asyncio.wait()方法实现协程，下面我们通过不同控制结构来实现协程，让我们一起来看看他们的不同作用吧～在多个协程中的线性控制流很容易通过内置的关键词await来管理。使用asyncio模块中的方法可以实现更多复杂的结构，它可以并发地完成多个协程。一、asyncio.wait()你可以将一个操作分..._python异步io之协程(二):使用asyncio的不同方法实现协程

reactos操作系统实现(162)_co_intcreatewindowex-程序员宅基地

文章浏览阅读2.2k次。co_IntCreateWindowEx函数主要用创建一个显示的窗口，具体实现代码如下：#001 HWND APIENTRY#002 co_IntCreateWindowEx(DWORD dwExStyle,#003 PUNICODE_STRINGClassName,#004 PUN_co_intcreatewindowex

opentsdb源码编译 本地调试环境搭建_opentsdb编译-程序员宅基地

文章浏览阅读895次。opentsdb源码编译 本地调试环境搭建opentsdb源码编译及调试环境搭建前言源码编译过程调试环境搭建opentsdb源码编译及调试环境搭建以下介绍opentsdb源码编译和本地调试环境搭建过程。官网地址: http://opentsdb.net/docs/build/html/development/development.html.前言OpenTSDB is a distrib..._opentsdb编译

pip 异常问题_pipexception:-程序员宅基地

文章浏览阅读2.1k次。使用pip安装出现报错 Exception:Traceback (most recent call last): File "C:\Users\csprock\Anaconda3\lib\site-packages\pip\basecommand.py", line 215, in main status = self.run(options, args) File "..._pipexception:

华为笔记本开发android,华为二合一笔记本支持Android可能是鸡肋！-程序员宅基地

文章浏览阅读923次。原标题：华为二合一笔记本支持Android可能是鸡肋！华为手机销量猛增无疑让华为高兴，不过面对华为提出提出其消费者BG要在5年内实现千万收入，压力颇大，单靠手机业务显然难以实现，在小米推出笔记本的示范效应下，华为推出笔记本是很正常的情况，在过去几年，华为一直都在学习小米的营销模式。 让人诧异的是华为的二合一笔记本产品是一个双系统产品，即是加上键盘是使用Windows系统的笔记本，拆掉键盘就是And..._android开发用华为笔记本怎么样

随便推点

HTML列表项目结点：HTMLCollection和NodeList-程序员宅基地

文章浏览阅读251次。HTMLCollection是元素集合(元素顺序为文档流中的顺序)，它和NodeList很像，有length属性来表示HTMLCollection对象的长度，可以通过 item() 传入数字索引来访问单个元素(也可通过方括号[ ]的方式)。当时它还有一个 nameItem() 方法，可以返回集合中指定 name 属性值 或 id 属性值的元素。HTMLCollection是即时更新的，当其所包含的..._html [object nodelist]

福音！GitHub开源中文版《Go入门指南》学习教程-程序员宅基地

文章浏览阅读975次。一个语言欢迎肯定有它独特的原因。比如Python作为胶水语言，上手快、使用简单、三方库资源丰富，机器学习的一些模型算法包，深度学习Tensorflow、Pytorch都是用Python来..._go语言基础 github

StringUtil和StringUtils的区别_stringutil和stringutils有啥区别-程序员宅基地

文章浏览阅读4.4k次。org.apache.commons.lang.StringUtils类是用于操作Java.lang.String类的，而且此类是null安全的，即如果输入参数String为null，则不会抛出NullPointerException异常。StringUtils类中有130多个静态方法，都可以通过如下方式调用：StringUtils.xxx()。_stringutil和stringutils有啥区别

STC的IAP功能使用_stc iap 全局中断-程序员宅基地

文章浏览阅读1w次，点赞3次，收藏33次。 以一些资料源自mcuol.com的xiaoxiaopig博客里面，http://blog.mcuol.com/User/xiaoxiaopig/Article/38135_1.htm，在此声明，如有意见，请立该联系处理。有空要加为好友∧＿∧　STC89C51、52内部都自带有2K字节的EEPROM，54、55和58都自带有16K字节的EEPROM，STC单片机是利用IAP技术实现的EEPROM，内部Flash擦写次数可达100，000 次以上，先_stc iap 全局中断

JS实现已知图片路径下载图片_js通过图片路径下载图片-程序员宅基地

文章浏览阅读1.4k次。<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <title>Title</title></head><body><button id="btn">jsdownload</button></body><script> const btn = documen_js通过图片路径下载图片

如何制作可用于Windows虚拟机的macOS安装镜像_esddmg-程序员宅基地

文章浏览阅读3.8k次。macOS系统的安装镜像文件默认都是dmg文件，不能直接使用于Windows下的虚拟机安装，所以需要制作成Windows下可以识别的ISO或者CDR格式。一、下载DMG安装镜像以下载 macOS Sierra为例，可以从苹果官网页面的第4节下载 macOS Sierra找到下载链接。二、在macOS中双击安装..._esddmg

推荐文章

热门文章

相关标签