有时候我们做一件事不因为它容易,而是因为它困难
看书都有半途而废的冲动,更何况是生活。看着算法导论,看着编译原理,哪些晦涩难懂的数学表达式,就是因为它难,所以我才更要学。
我的文章是没有多少点赞,我的视频是没有多少播放。有时候也在难,搞个噱头,做个什么40k前端面试指南,搞个程序员人生解惑?
这是我的长期主义吗?
我学习的目的是什么?单纯为了好的面试表现,我觉得不是,我觉得哪些是有意义的,传播知识,传播方法论可以,做自己的开源项目可以。坚持下去,与君共勉!!!!
所有的问题都很复杂,我经常在想,我这么牛逼,搞个项目,找个人哪怕做外包都比南京百分之90公司强,我为什么没有做起来? 我没有销售,没有人际。
所有问题混在一起看,都很复杂,都很繁琐。解决问题的第一步就拆分问题,第二步就是细化问题。
一个算法问题,首先就应该是划分类型,在这个类型里面去细化场景与实现。
分治法核心我个人觉得是把一个复杂的问题拆解成多个相同的小问题。
里面两个关键点,第一需要拆解成小问题,第二个变成相同的问题。
核心思想是归纳法。
let array = new Set();
for (let i = 1; i <= 10; i++) {
array.add(parseInt(Math.random() * 100));
}
const targetList = Array.from(array);
console.log("targetList", targetList);
function quickSort(targetList) {
if (targetList.length <= 1) {
return targetList;
}
const pivot = targetList[0];
const left = [];
const right = [];
for (let i = 1; i < targetList.length; i++) {
if (targetList[i] < pivot) {
left.push(targetList[i]);
} else {
right.push(targetList[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log("res", quickSort(targetList));
结束
是不是一个二分法的衍生熟悉的场景,\log_2(n),是我们的执行层数,每一层执n次,显然结果出来是:n*\log_2(n)。
有时候最好就是平均,每次的数据都是随机的,我们的大部分执行结果去趋近这个最好状态的。
正因为上面的情况,数据有本身的特殊性,可能本身数据就是一个有序的数组,算法里面开始也没有进行有序性的校验,再我们执行的过程中就会出现最差的情况。
怎么去避免呢?随机化,每次比较的值都是不确定的,也不一定取第一个。 在有序数据的场景下面,随机化能带来巨大的收益。
let array = [];
const count = 1000;
for (let i = 1; i <= count; i++) {
// array.add(parseInt(Math.random() * count));
// array.push(parseInt(Math.random() * count));
array.push(i);
}
// const targetList = Array.from(array);
const targetList = array;
// console.log("targetList", targetList);
// 普通快排
function quickSort(list) {
const targetList = [...list];
if (targetList.length <= 1) {
return targetList;
}
const pivot = targetList[0];
const left = [];
const right = [];
for (let i = 1; i < targetList.length; i++) {
if (targetList[i] < pivot) {
left.push(targetList[i]);
} else {
right.push(targetList[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
// console.log("res", quickSort(targetList));
console.time("quickSort");
// console.log("quickSort", quickSort(targetList));
quickSort(targetList);
console.timeEnd("quickSort");
// 随机快排
function randomQuickSort(list) {
const targetList = [...list];
if (targetList.length <= 1) {
return targetList;
}
const random = Math.floor(targetList.length * Math.random());
// console.log("random", random, "length", targetList.length);
// const random = Math.floor(targetList.length / 2);
const pivot = targetList[random];
const left = [];
const right = [];
for (let i = 0; i < targetList.length; i++) {
if (i === random) {
continue;
}
if (targetList[i] < pivot) {
left.push(targetList[i]);
} else {
right.push(targetList[i]);
}
}
return [...randomQuickSort(left), pivot, ...randomQuickSort(right)];
}
console.time("randomQuickSort");
// console.log("randomQuickSort", randomQuickSort(targetList));
randomQuickSort(targetList);
console.timeEnd("randomQuickSort");
结论