算法

Python 实现 KNN 分类算法

0 条评论 算法 Python 算法 shenke

本文将详细讲述 KNN 算法及其 python 实现

1. KNN

KNN(K-Nearest Neighbour)即 K最近邻,是分类算法中最简单的算法之一。KNN 算法的核心思想是 如果一个样本在特征空间中的 k 个最相邻的样本中的大多数属于某一个类别,则将该样本归为该类别

1.1 KNN 分类算法步骤

有 N 个已知分类结果的样本点,对新纪录 r 使用 KNN 将其分类

  • 1.确定 k 值,确定计算距离的公式,如常用欧氏距离 $d(x,y)=\sqrt{\displaystyle \sum^n_{i = 1}{{(x_i-y_i)}^2}}$
  • 2.计算 r 和其他样本点之间的距离 $d_{ir}$,其中 $i\in(1,N)$
  • 3.得到与 r 最接近的 k 个样本
  • 4.将 k 个样本中最多归属类别的分类标签赋予新纪录 r,分类结束


Java 求最大子数组

0 条评论 算法 Java 算法 shenke

Background

在某天购入股票后抛出,求如何取得最大利润。已知股票趋势如图所示。


Java 分治策略实现归并排序

0 条评论 算法 Java 算法 shenke

Thought

能不能使用分治策略的关键是 子问题的最优解是否可以通过某种手段得到原问题的最优解。对于归并排序,将两个已经有序的子问题序列进行合并,就可得到一个有序序列,以此类推,最终可将所有子问题序列合并成一个有序序列,而得到的有序序列就是最终答案。

图片来自简书,链接:https://www.cnblogs.com/chengxiao/p/6194356.html


Java 分治策略实现快速排序

0 条评论 算法 Java 算法 shenke

Thought

  • Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray ≤ x ≤ elements in upper subarray.
  • Conquer: Recursively sort the subarrays.
  • Combine: Trivial.

以枢轴 x 为中点,每次排序将小于枢轴 x 的元素都放在 x 左边,大于 x 的元素都放在 x 右边,然后递归以同样方式对子数组排序


Java 建立大顶堆

0 条评论 算法 Java 算法 shenke

Thought

  • 从最后一个有孩子的父节点开始调整,若父节点的值小于左右孩子结点的值(如果有的话),就与该孩子结点交换位置。若发生了交换,由于原来父节点到了他的孩子结点上,可能破坏了现在这颗以原来父节点为根节点的子树,所以需要重复以上步骤,即递归。
  • 数组的范围是从 0 ~ length - 1,设父节点的下标为 p,则:
p的左孩子下标为:2 * p + 1
p的右孩子下标为:2  *p + 2

最后一个有孩子的父节点下标为(length - 2)/ 2