编写程序前一定要对程序是否有解、可解、以及大概需要运行多久做到心中有数。这个问题的关键是通常通过问题的可计算性和算法复杂度评估。
算法复杂度估算
算法复杂度是衡量算法效率的重要标准。首先要了解现代计算机的性能上限：
1) 普通家用计算机（主频约3GHz）可执行 10^9 ～ 10^10 条指令/秒；
2) 多核PC/服务器：几十到上百核，约 10^11～10^12 条指令/秒。
3) 超级计算机：达到百亿亿次级别，浮点运算约10^18 次/秒（FLOPS, Floating-point Operations Per Second），指令吞吐量在 10^17～10^18 条/秒 量级。
在算法竞赛和算法分析中，通常保守地按 1 秒约 10^8 次基本操作来估算。
不同算法复杂度在不同规模问题下的计算次数（其中若1.e+5形式，实际表示若1.0×10^5）
| 问题规模 n | 多项式函数 logn |
多项式函数 n |
多项式函数 nlogn |
多项式函数 n^2 |
多项式函数 n^3 |
指数函数 2^n |
指数函数 n! |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 1 | 2 | 1 |
| 10 | 3.32 | 10 | 33.21928095 | 100 | 1000 | 1024 | 3628800 |
| 20 | 4.32 | 20 | 86.4385619 | 400 | 8000 | 1048576 | 2.4e+18 |
| 30 | 4.91 | 30 | 147.2067179 | 900 | 27000 | 1.0e+9 | 2.6e+32 |
| 40 | 5.32 | 40 | 212.8771238 | 1600 | 64000 | 1.0e+12 | 8.1e+47 |
| 50 | 5.64 | 50 | 282.1928095 | 2500 | 125000 | 1.1e+15 | 3.0e+64 |
| 100 | 6.64 | 100 | 664.385619 | 10000 | 1000000 | 1.2e+30 | 9.3e+157 |
由此，可以通过问题规模和代码的算法复杂度，大致推断代码的运行时间量级。
P NP NP-Complate NP-Hard问题
确定性图灵机（DTM）和非确定性图灵机（NTM）都是理论计算机科学中的抽象计算模型。它们不是真实的电脑，而是用来严格定义可计算和计算复杂度的工具。
一台图灵机通常包括：一条无限长的纸带，分成一个个格子；一个读写头，可以读、写、左右移动；一个有限状态控制器；一个转移函数，决定下一步做什么。其核心就是转移函数。根据当前状态和读写头读到的符号，决定下一步，写什么符号，移动到哪个状态，读写头向左还是向右移动。
在计算复杂性理论中，讨论DTM和NTM时，图灵机是判定器，输入是一个有限字符串，图灵机会进入接受状态或拒绝状态，作为判定器我们可以以此表示判定结果接受或拒绝。
Σ 是有限字母表，比如 {0,1}。
L 是 Σ∗ 的一个子集，L⊆Σ∗。
输入x∈Σ∗。
如果 x∈L，答案是“是”，图灵机接受；
如果 x∉L，答案是“否”，图灵机拒绝。
确定性图灵机（DTM）
确定性图灵机对于每一个当前状态和当前读到的符号，转移函数最多给出一个确定的下一步动作。确定性图灵机就像普通程序，每一步都明确知道下一步该做什么。给定相同输入，它永远得到相同结果。
最多也意味着可能某个状态下没有定义，则图灵机在该状态下进入停机状态。停机和拒绝不等价，运算完成即为停机。
非确定性图灵机（NTM）
非确定性图灵机对于每一个当前状态和当前读到的符号，转移函数可以给出零个、一个或多个可能的下一步动作。非确定性图灵机直观上理解为一种计算树的运算，存在一条计算路径到达接受状态则接受，所有路径都拒绝才拒绝。需要注意的是：存在一条路径，对应数学概念上的存在∃，不等同于遍历多条路、在多条路随机选择一条路、同时并行验证所有解。
P类问题（Deterministic Polynomial time）
多项式时间可解的问题。存在一个确定性图灵机，能在多项式时间内判定该问题。 典型例子：排序、二分查找、最短路径、最大流、线性规划、素数判定（2002 年 AKS 算法证明属于 P）
NP问题（Nondeterministic Polynomial time）
可以在多项式时间内验证候选解的问题。存在一个非确定性图灵机，能在多项式时间内判定该问题。
典型例子：
SAT：给一个布尔公式，是否存在一组变量赋值使它为真？
旅行商判定：是否存在一条长度不超过 K 的回路？
子集和：是否存在一个子集，其和等于目标值？
图着色：能否用 k 种颜色给图着色？
NP完全（Nondeterministic Polynomial Time Complete）
属于NP，且所有NP问题都能多项式时间归约到它。是NP中最难的问题。例子：SAT、旅行商判定、背包判定、图着色等。如果任何一个NP完全问题有多项式算法，则P=NP。
NP难（Nondeterministic Polynomial Time Hard）
至少和NP中所有问题一样难，但不一定属于NP。不要求多项式时间可验证。例子：停机问题、TSP优化、SAT的某些推广。NP完全 = NP ∩ NP难。
P⊆NP
NP完全⊆NP
NP完全⊆NP难
NP完全=NP∩NP难
小结
很多NP完全问题目前最好的精确算法就是指数级或阶乘级，实际中遇到 NP完全或 NP难问题，通常不会去求精确最优解，而是用近似算法、启发式算法、限制问题规模、利用特殊结构或者接受指数时间，只处理小规模输入。P 是容易解的；NP 是容易验证的；NP完全是 NP 中最难的一类；NP难是至少和 NP完全一样难、但不一定在 NP 里的问题。P 是否等于 NP，是计算机科学最大的未解难题之一，目前学术界普遍猜测但尚未证明P ≠ NP。