c++ 数据结构与算法 第四版
2018-10-28 20:15:48 weixin_43462819 阅读数 289

之前学习过算法第四版,但隔了有一段时间。现在准备重新复习一遍。因为书上的代码都是用JAVA写的,我这里准备给出每个算法的C++实现,同时给出算法的复杂度分析。
github地址:https://github.com/Nwpuer/algs4-in-cpp

2019-07-12 18:47:31 V2636011127 阅读数 6

算法
计算机算法解决计算问题时,能够给出正确的答案,有效的利用资源。
正确性:我们通常会精确的定义一个正确的解决方案设计的内容。然而对于某些算法很难判定是否给出了正确答案。不过我们可以接受可能会产生的错误算法,只要这个算法的错误频率在可被控制的范围之内。对于另外一种算法—近似算法,正确性也是一个需要重考量的问题。近似算法适合于优化问题。即根据一些量化测度来寻找最优解的问题。“近似最优”就是近似算法输出的解的量化测量值介于最优解的量化测量值的一个已知因子之内。只要指定了目标因子,我们就可以说一个近似算法的正确解是任意一个量化测度值在最优解目标因子之内的解决方案。
资源利用:针对一个可以输出正确值的算法,时间便是我们用来衡量算法效率的主要方式,但不是唯一。由于一个算法必须在可用的内存空间上运行因此我们还需要考虑算法需要占用多大的内存空间,除此之外还需要考虑:网络通信,随机比特,磁盘操作。算法运行的时间还与算法本身之外的几个因素有关:计算机的速度,实现算法的编程语言,编译器或者解释器,程序员编写程序的技术,正运行的程序并行执行其他进城。为了衡量一个算法的速度,我们需要确定算法的输入规模其次是随着输入规模的增加,表示运行时间的函数如何增长,运行时间的增长速率。我们仅仅只关心时间的增长量级。为了表示一项任务所花的时间,我们必须做出一些简单的假设。我们假定每步单独的操作—无论是一个算术运算,比较,变量赋值,给数组标记索引操作,或者是程序调用,从程序中返回操作结果—均会花掉不依赖于输入规模的固定时间。操作不同,各个操作所花费的时间可能不同,但放一个步骤仅仅是有多个简单的操作叠加而成时,该步骤会花费常量时间,我们约定执行第i步所花费的时间为t,其中t是不依赖于输入规模所输入的规模n的常量。

c++ 数据结构与算法 第四版 相关内容

2019-07-01 16:50:32 V2636011127 阅读数 21

大O表示Ω\Omega表示定义:
若存在正数c和N,对于所有的n>=N,有f(n)>=cg(n),则f是g的大Ω\Omega表示
若存在正数c和N,对于所有的n>=N,有f(n)<=cg(n),则f是g的大O表示

c++ 数据结构与算法 第四版 相关内容

2018-11-21 18:33:10 weixin_43526074 阅读数 76

https://blog.csdn.net/weixin_36888577/article/details/79937886
股票买卖专题
https://blog.csdn.net/humanleelxy/article/details/78420274

零碎的C++知识

精度

float有7尾有效数字
double有16位
移位操作:>> 右移 数字变小 7变3

C++引用变量

https://blog.csdn.net/qq_40873884/article/details/79632314
值传递
void Swap(int a, int b)
Swap(a, b);
指针传递
void Swap(int* a, int* b)
Swap(&a, &b);
引用传递
void Swap(int& a, int& b)
Swap(a, b);
新型引用+值传递
int Swap(const int& ra);
Swap(ra);

引用变量作为返回值 注意传入int& Swap(int& a, int& b) return a;int m=Swap(a, b); 或者传入全局变量或静态变量

const不可改变的变量
static只初始化一次,a++会一直加下去,调用一次函数加一次
在这里插入图片描述

struct结构体 重载运算符

struct point
{
int elem;
bool operator==(const point b) const
{
return this->elem == b.elem;
}
}

面向对象的抽象封装继承多态(刷题用不到就不写了)

指针(不知道要用到多少 复制构造函数、析构函数、函数引用变量、函数指针)

STL容器(即数据结构)

概述

  1. vector deque
  2. list set multiset map multimap
  3. stack queue priority_queue
    empty() max_size() size() swap() operator=
    六个关系运算符(priority_queue除外)
    begin() end() rbegin() rend() erase() clear()(stack queue priorty_queue除外)
    迭代器:指针地址 i++,=赋值 == !=(23可用)
    <= i+=n i[n] (3可用 比较大小,加n,取n)

vector

声明和初始化
vector v1;
v1.push_bach(1); #逐个加入 (0 1 2 3 4 5)
v1(3,5) #数字重复初始化3个5 (5 5 5)
vector ::iterator i1=v1.begin()+1;
v2(i1, i1+3) #迭代器初始化 (1 2 3)

增加元素
v.insert(v.end(), 和上面一样) #前面索引插到前面 后面索引插到后面 assign同样

删除元素
v.erase(v4.end()-2)
v.erase(v.begin()+2) #注意单个元素删去第二个元素,v.begin()会报错
v.erase(v.begin(), v4.end()-2) # begin end 头尾都要 begin begin 要头不要尾 end end 要尾不要头

取其中元素
v1[1] v1.at(1) #1
vector v11(v1.begin()+1,v1.end()-2); #取一段元素 begin end 头尾都要 begin begin 要头不要尾 end end 要尾不要头

改变capacity和size
v.reserve(6)
v.resize(7) #补0
v.clear() #相当于v.resize(0)

转置元素
printVector(“v4”,v4); // v4 = (1 2 3)
vector::reverse_iterator i3 = v4.rbegin();
for ( ; i3 != v4.rend(); i3++)
cout << *i3 << ’ '; // print: 3 2 1
cout << endl;

算法(非成员函数)
replace(v.begin(),v.end(),0,7) #0全部换成7 包括开头包括结尾
replace_if(v.begin(),v.end(),f1,7) #函数返回bool 接受一个值
sort(v5.begin(),v5.end(),greater()); #降序 默认升序 sort的取片也和上边一样
在这里插入图片描述
在这里插入图片描述

stack queue priority_queue deque

stack

push; top; pop; empty; size
stack stack1; #默认为双端队列
stack<int, vector> stack2;
stack<int, list> stack3;
for(int j=0;j<9;j++){
stack1.push(j);
}
while(!stack1.empty()){
cout<<stack1.size()<<endl;
cout<<stack1.top()<<endl;
stack1.pop();
}
在这里插入图片描述

queue

push front back pop empty size
除了front和back其他的都和stack一样。

priority_queue

默认用vector实现,默认大数先出。
push top pop empty size
注意虽然叫priority_queue成员函数却和stack一样,是top。
priority_queue <int, vector, less > pq1;
priority_queue <int, vector, greater > pq2;
int a[]={4,6,1};
priority_queue pq3(a,a+3);

deque

综合了vector可以访问任意位置元素和list高效插入删除的优点。
在这里插入图片描述
在这里插入图片描述

list 刷题好像不常用到就不写了

STL算法

sort(begin,begin+N,f) 返回bool类型 接收函数类型和begin、begin+N相同 切块还是和以前一样
reverse(begin,begin+N)

bool ff(int a,int b){
    return a<b;
}
int a[5]={1,2,3,4,5};
reverse(a,a+5);  //54321
sort(a,a+5,ff);  //12345

string.h库

#include <string.h>
#include <string>
cin>>s; #string string
cout<<s; #string遇到空格结束依次输入
printf("%s",b.c_str());
string str;
str.assign(100,'\n'); //这里初始化一个大笑为100的,内容为‘\0'的字符串数组。
scanf("%s",str.c_str()); #遇到空格结束依次输入
getline(cin,str); #接受空格
printf("%c\n",str[2]);

if(str1.find("aaaa") != string::npos)
        cout<<"有"<<endl;
    else
        cout<<"没有"<<endl;

https://www.cnblogs.com/X-Do-Better/p/8628492.html
https://blog.csdn.net/superna666/article/details/52809007
string find
http://www.cnblogs.com/bhd123/p/9453662.html

oj常见错误提示
https://blog.csdn.net/coral_yms/article/details/25161069

算法设计与数据结构】为何程序员喜欢将INF设置为0x3f3f3f3f?
https://blog.csdn.net/jiange_zh/article/details/50198097

c++ 数据结构与算法 第四版 相关内容

2019-06-26 18:48:40 V2636011127 阅读数 14

大O表示法
最常用来描述渐进复杂度引入大O表示法,给定两个正值函数f和g。
定义:
如果存在正数c和N,对于所有的n>=N,有f(n)<=cg(n),则f(n)=O(g(n)).
上述定义表明,如果对于足够大的n(或大于某自然数的N的n)存在正数c时f不大于cg,则f为g的大O表示法
f(n)=2n2+3n+1=O (n2)
为了选择更好的c和N,规定某个N值,f中的某项应该时最大项,在等式中只有2n2和3n可能是最大项,但是当n>1.5时,2n2>3n,他们都与同一函数对g(n)=n2和f(n)有关,对于固定的g,可以得出无穷多的常数对c和N,关键在于g和f以相同速率增长。大O表示中固有的不精确性还会导致其他问题,所以大O表示法定义中的f(n)用n2代替,n2为f(n)的大O表示
2n2+3n+1<=cn2
大O表示法的性质

  1. (传递性)如果f(n)=O(g(n)),g(n)=O(h(n)),那么f(n)=O(h(n))(或者O(O(g(n)))=O(g(n)))
    证明:
    根据定义若存在正数c1和N1,对于所有的n>=N1,有f(n)<=c1g(n),则f(n)=O(g(n));同样,若存在正数c2和N2,对于所有n>=N2,有g(n)<=c2h(n),则g(n)=O(h(n))。因此,对于所有n>=N,其中N为N1与N2中的较大者,有c1g(n)<=c1c2h(n),只要取c=c1*-c2,则对于所有的n>=N有f(n)<=ch(n),即f(n)=O(h(n))。
  2. 如果f(n)=O(h(n)),g(n)=O(h(n)),则f(n)+g(n)=O(h(n))
    证明:
    令c=c1+c2,则有f(n)+g(n)<=ch(n)。
  3. ank=O(nk)
    证明:
    令c>=a,不等式ank<=cnk恒成立。
  4. 对于任何正数j,nk=O(nk+j)。
    证明:
    令c=N=1,成立
    从上面的性质可以推出,任何多项式都是该多项式中次数最高的大O表示。
    对数函数是算法效率评估中一个非常重要的函数。实际上,如果算法复杂度是一个对数函数,那么该算法非常好
    性质:
  5. 如果f(n)=cg(n),则f(n)=O(g(n)).
  6. 对于任何正数a和b(b!=1),loga(n)=O(logb(n))。
    该性质说明对数函数之间存在对应关系,性质6表明,无论底数为何,对数函数互为大O表示也就是说所有的对数函数有相同的增长速度。
  7. 对于任何正数a!=1,loga(n)=O(lg(n)),其中lg(n)=log2(n)。

c++ 数据结构与算法 第四版 相关内容

复杂度示例:

博文 来自: V2636011127
没有更多推荐了,返回首页