[IMUDGES内部培训]概述

发布于 2018-11-04  29 次阅读


什么是程序

程序=数据结构+算法

数据结构是存储组织数据的方式,而算法是是解决特定问题的步骤和方法. 
我们主要着重讲解算法,顺带会讲解算法中所使用的数据结构.

数据结构

  • 线性表
  • 集合

什么是程序设计竞赛

顾名思义,程序设计竞赛就是以程序设计为主题举办的竞赛。而我们平常参加的acm,省赛,校赛之类的都属于解题竞赛。 
解题竞赛在开始时会告知选手题目的数量,选手的目标是解决其中尽可能多的题目。程序设计竞赛中题目的形式如下。

  1. 描述
  2. 输入
  3. 输出
  4. 样例输入
  5. 样例输出

程序的运行一般是有时间和空间限制的。在大多数比赛中,运行时间限制在1秒。一旦程序运行的时间或内存超过了限制,程序就会被强行结束,当做不正确的解答处理。因此,在比赛中还必须考虑高效的解法。

由此,可以说程序设计竞赛是综合了以下两个要素的复合竞赛:

  • 设计高效且正确的算法
  • 正确地实现

并且,为了设计算法,一些算法的基础知识也是必不可少的。

算法复杂度

在设计满足问题要求的算法时,复杂度的估计是非常重要的.我们不可能把所有想到的算法都去实现一下.应该通过估算来判断算法是否足够高效.

算法复杂度分为时间复杂度和空间复杂度。最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。 
简单来说,时间复杂度指的是语句执行次数,空间复杂度指的是算法所占的存储空间.

运行时间不光取决与复杂度,也会受到循环体复杂度等因素的影响,但这种影响最多也就几十倍.

常见复杂度

常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n^2),立方阶O(n^3),…,k次方阶O(n^k),指数阶O(2^n),o(n^n)

复杂度举例

sum = n*(n+1)/2;
for(int i = 0; i < n; i++){<br>
    cout<<i<<endl;<br>
}                       
for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        cout<<0<<endl;
    }
}     
for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        printf("%d ",i);
    }
}   
int i = 1, n = 100;
while(i < n){
    i = i * 2;
}

关于stl

STL是指C++的标准模板库(Standard Template Library)。它很好用,但也很复杂。可以大大降低比赛时的代码量,但是有些情况下效率不行,需要自己写相应的算法. 
课上学相应的内容时,别用stl,被老师骂了不管

常用stl举例

数据结构:

  • stack
  • queue (priority_queue) (deque)
  • bitset
  • list
  • vector
  • map (multimap)
  • set (multiset)
  • string

算法:

  • fill
  • unique
  • sort
  • partition (stable_partition)
  • sort (stable_sort)(partial_sort)
  • lower_bound (upper_bound)
  • binary_search
  • next_permutaiton
  • set_*
  • swap

技巧