读 Christoph Durr & Jill-Jenn Vie《高效算法——竞赛、应试与提高必修 128 例》

目录

1. 技巧
   1. 输入输出
   2. 找最大最小值
   3. 二分法
   4. 复杂度

技巧

输入输出

stdin.readline() 函数读标准输入的效率是 input() 函数的 4 倍。 —— 第一章 引言 p7

如果程序在读数据时遇到性能问题，可以仅使用一次系统调用，把整个输入文件读入，速度可以提升 2 倍。（当然，它们的区别是 input 返回的字符串不带换行符）

比如有 n 行输入，每行都是整数。

import os
inputs = list(map(int, os.read(0, M).split()))

这里 M 是一个超过文件大小的整数，是读入的最大长度。map 函数把 int() 应用在每个输入上，把他们转化成整数。

找最大最小值

max((l[i], i) for i in range(len(l)))

这个方法可以直接得到最大值和最大值的下标记，太简洁了，来自 p 18 (如有重复值就取到下标最大的)

但是不知这样是否会耗费额外内存呢？

二分法

python 标准库 bisect 提供二分查找和插入

二分查找

import bisect

bisect.bisect 就是 bisect.bisect_right 的别名。 bisect_right(list, n)，返回是第一个大于 n 的值的下标。

另外还有 bisect_left

插入

insort_left 和 insort_right 可以直接把一个值插入到数组中。

这些函数还接收另外两个参数 lo 和 hi 例如， bisect.bisect(seq, item, lo = 0, hi =len(seq))

python 3.8 bisect 官方文档

我的博客中使用该库的题目列表

复杂度

P 问题和 NP 问题

在计算机领域，一般可以将问题分为可解问题和不可解问题。不可解问题也可以分为两类：一类如停机问题，的确无解；另一类虽然有解，但时间复杂度很高。可解问题也分为多项式问题(Polynomial Problem，P问题)和非确定性多项式问题(NondeterministicPolynomial Problem，NP问题)。（摘自百度百科）