package array_problem;


/**
 * 什么是算法面试？
 *      1、不代表能够"正确"回答每一个算法问题，但是合理的思考方向其实更重要，
 *      也是正确完成算法面试的前提。
 *      2、算法面试优秀并不意味着技术面试优秀，而技术面试优秀也并不意味着能够拿到 Offer。
 *      3、把面试的过程看作是和面试官一起探讨一个问题的解决方案。对于问题的
 *      细节和应用场景，可以和面试官沟通。而这种沟通本身也是非常重要的，它暗示着
 *      你思考问题的方式。
 *      4、如果是非常难的问题，对于你的竞争对手来说，也是难的。关键在于你所表达出的解决问题的思路。
 *      甚至通过表达解题思路的方向，得出结论：这个问题的解决方案，应该在哪一个领域，我们可以通过查阅
 *      或者进一步学习解决问题。
 *
 * 例如：对于一组数据进行排序？
 *      思考：这组数据有什么特征？
 *      1）、有没有可能包含有大量重复元素？如果有这种可能的话，三路快排是更好的选择。否则使用普通快排即可。
 *      2）、是否大部分数据距离它正确的位置很近？是否近乎有序？如果是这样的话，插入排序是更好的选择。
 *      3）、是否数据的取值范围非常有限？比如对学生成绩排序，如果是这样的话，计数排序是更好的选择。
 *      4）、是否需要稳定的排序？如果是的话，归并排序是更好地选择。
 *      5）、是否是使用链表存储的？如果是的话，归并排序是更好地选择，因为快排非常依赖于数组的随机访问。
 *      6）、数据的大小是否可以装载到内存里？不能的话，需要使用外排序。
 *
 * 如何准备算法面试？
 *      在学习和实践做题之间，要掌握平衡。
 *
 * 如何回答算法面试问题？
 *      1、注意题目中的条件，例如：
 *          1）、给定一个有序的数组。
 *          2）、设计一个 O(nlogn) 的算法。
 *          3）、无需考虑额外的空间。
 *          4）、数据规模大概是10000。
 *      2、当没有思路时：
 *          1）、设计几个简单的测试用例，试验一下。
 *          2）、不要忽视暴力解法。暴力解法通常是思考的起点。
 *      3、优化算法
 *          1）、遍历常见的算法思路。
 *          2）、遍历常见的数据结构。
 *          3）、空间和时间的交互（哈希表）。
 *      4、预处理信息（排序）。
 *      5、在瓶颈处寻找答案：O(nlogn) + O(n^2)、O(n^3)。
 *      6、实际编写问题：
 *          1）、极端条件的判断：数组为空？字符串为空？数量为0？指针为 NULL？
 *          2）、合理的变量名。
 *          3）、注意代码的模块化、复用性。
 *
 * 一、时间复杂度
 * 1、到底什么是大 O？
 *      n 表示数据规模，O(f(n)) 表示运行算法所需要执行的指令数，和 f(n) 成正比。
 * 2、数据规模的概念——如果想在1s之内解决问题：
 *      1）、O(n^2) 的算法可以处理大约10^4级别的数据。
 *      2）、O(n) 的算法可以处理大约10^8级别的数据。
 *      3）、O(nlogn) 的算法可以处理大约10^7级别的数据。
 * 3、空间复杂度
 *      1）、多开一个辅助的数组：O(n)。
 *      2）、多开一个辅助的二维数组：O(n^2)。
 *      3）、多开常数空间：O(1)。
 *      4）、递归是有空间代价的，递归 n 次，空间复杂度就为 O(n)。
 * 4、简单复杂度分析
 *      经过几次"除以2"操作后，等于1，此时的算法是对数复杂度的，并且对数复杂度会忽略它的底。
 *
 * 5、亲自试验自己算法的时间复杂度
 *      O(log(n)) 与 O(n) 有着本质的差别。
 *
 * 6、递归算法的复杂度分析
 *      1）、不是有递归的函数就是一定是 O(nlogn) 的。
 *      2）、递归中进行一次递归调用：递归函数的时间复杂度为 O(T * depth)。
 *      3）、递归中进行多次递归调用：画出递归树，计算调用次数。
 *      例如2次递归调用：2^0 + ... 2^n = 2^(n+1) - 1 = O(2^n)
 *      4）、主定理：归纳了递归函数所计算时间复杂度的所有情况。
 *
 * 7、均摊时间复杂度分析（Amortized Time Analysis）与 避免复杂度的震荡
 *      见 array package
 *
 * JsonChao的数组核心题库：36题
 */
public class Main {

    public static void main(String[] args) {

    }
}
