{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Примеры задач/вопросов по k-NN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 1\n",
    "Пусть на плоскости дано два объекта двух разных классов. <br/>\n",
    "Покажите, что если выполнять классификацию методом 1-NN с евклидовым расстоянием, то разделяющей границей между классами будет прямая линия."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 2\n",
    "\n",
    "Пусть даны следующие точки в одномерном пространстве:\n",
    "$$X = [1,2,4,8,16,32]$$\n",
    "с соответствующими метками классов:\n",
    "$$y = [1,2,2,1,2,1]$$\n",
    "\n",
    "Обозначим через $x^*$ объект, для которого необходимо выполнить классификацию, а через $a(x)$ - алгоритм, в соответствии с которым выполняется классификация.\n",
    "\n",
    "Найдите и выпишите границы классов, если $a(x)$ это\n",
    "1. 1-NN\n",
    "2. 2-NN\n",
    "3. 2-NN, с весами обратно пропорциональными расстоянию до ближайших соседей\n",
    "4. 3-NN\n",
    "\n",
    "Для всех $a(x)$ мера близости - евклидова. В случае равнозначности, выставляется класс с наименьшей меткой."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 3\n",
    "Перечислите все числовые гиперпараметры метода k-NN и определите как они влияют на переобучение/недообучение"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 4\n",
    "По графику ниже выполните регрессию точки с координатой в $x=3.5$ с помощью взвешенного метода k-NN, где $k=3$, расстояние - евклидово, а вес $i$-го ближайшего соседа определяется как\n",
    "$$w_i = \\frac{k - i + 1 }{ k }$$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAhUAAAF5CAYAAAAoOtjCAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAAPYQAAD2EBqD+naQAAIABJREFUeJzt3X905Xdd5/HXuxStU9ayRxgC0pGyIBarlSkgYYUeFia1\nOaffgus2bWf8kZyK1UyXE9eMdAtmlLNChq10TYGzB6L8mHKR3SOB7gpkoLoaftjTXKhiGxEoBAtt\nSVmL9goL7Xv/uHfC/ZGZSb7zzfeTz+fzfJyTo/NN7pz30xub93zv93tj7i4AAIDTdUboAQAAQBpY\nKgAAQCVYKgAAQCVYKgAAQCVYKgAAQCVYKgAAQCVYKgAAQCVYKgAAQCVYKgAAQCVYKgAAQCV2xFJh\nZi8ysw+a2b1m9qiZFRt8ze+a2VfNrGVmx8zsGSFmBQAAG9sRS4WksyV9RtKvSxr4ZSRm9luSDkp6\npaTnS3pY0kfM7PvqHBIAAJyY7bRfKGZmj0p6ubt/sOvYVyW90d3f1PnzD0q6X9Ivufv7wkwKAAC6\n7ZQzFSdkZudJGpL0sePH3P2bkv5K0nCouQAAQK8dv1SovVC42mcmut3f+RwAANgBzgw9wHYwsx+S\ndImkL0n6VthpAACIylmSnibpI+7+4FYeGMNScZ8kk/Qk9Z6teJKkT5/gMZdIumWb5wIAIGX7Jb1n\nKw/Y8UuFu99jZvdJeqmkv5bWL9T8aUlvPsHDviRJR48e1fnnn1/HmMFMTU3pTW96U+gxapFLK51p\noTMtOXTefffdOnDggNT5WboVO2KpMLOzJT1D7TMSkvR0M7tQ0jfc/SuSbpL0GjP7vNqRr5P0D5I+\ncIK/8luSdP7552vv3r3bOXpw55xzTvKNx+XSSmda6ExLLp0dW758YEcsFZKeK+nP1L4g0yXd2Dn+\nTkkT7n7EzHZJ+u+SHi/pLyVd6u7/L8SwO8l9990XeoTa5NJKZ1roTEsunWXtiKXC3f+PTnEnirsf\nlnS4jnlicu+994YeoTa5tNKZFjrTkktnWTHcUoqTuOiii0KPUJtcWulMC51pyaWzLJaKyF111VWh\nR6hNLq10poXOtOTSWdaOe5vuKpjZXknLy8vLOV1QAwDAaWs2m8fPyFzk7s2tPJYzFQAAoBIsFZEb\nHx8PPUJtcmmlMy10piWXzrJYKiI3MjISeoTa5NJKZ1roTEsunWVxTQUAAFjHNRUAACA4lgoAAFAJ\nlorILS0thR6hNrm00pkWOtOSS2dZLBWRO3LkSOgRapNLK51poTMtuXSWxYWakWu1Wtq1a1foMWqR\nSyudaaEzLTl0cqFmxlL/5u6WSyudaaEzLbl0lsVSAQAAKsFSAQAAKsFSEbnp6enQI9Qml1Y600Jn\nWnLpLIulInJ79uwJPUJtcmmlMy10piWXzrK4+wMAAKzj7g8AABAcSwUAAKgES0XkVlZWQo9Qm1xa\n6UwLnWnJpbMslorIHTp0KPQItcmllc600JmWXDrL4kLNyK2urmZzNXIurXSmhc605NCZxYWaZvY4\nM7vJzL5kZi0zWzKz54aeK7TUv7m75dJKZ1roTEsunWVFs1RImpf0Ukn7JV0g6Zikj5rZk4NOBQAA\nJElnhh5gM8zsLEk/J+kyd/945/DvmNllkn5N0m8HGw4AkLZjx6QHHhg8vnu3tG9f/fPsYLGcqThT\n0mMkfbvv+L9I+pn6x9k5ZmdnQ49Qm1xa6UwLnZE7dkwaGZEOHJAOHNBs53/qwIH28WPHQk+4o0Sx\nVLj7P0v6pKTXmtmTzewMMzsgaVhS1i9/tFqt0CPUJpdWOtNCZ+T6zlAMVG50BiNj0dz9YWbnSfpD\nSRdL+q6kpqTPqX116o/3fW02d38AALbRLbe0z0qcyNGj0v799c1Tgyzu/nD3e9z9JZLOlnSuu79A\n0vdJ+uKJHjM6OqqiKHo+hoeHtbCw0PN1i4uLKopi4PGTk5Oan5/vOdZsNlUUhdbW1nqOz8zMDJz+\nW11dVVEUA2+WMjc3N/Cb7lqtloqi0NLSUs/xRqOh8fHxgdnGxsbooIMOOuios0PSQt+xxb/5m/g6\nup6PRqOx/rNxaGhIRVFoampq4DGbFc2Zin5m9q/VXih+093n+z7HmQoAwOnjTEWaZyrMbMTMLjGz\np5nZPkm3SbpL0jvCThZW/8abslxa6UwLnWnJo7K8aJYKSedIerOku9VeJP5C0s+6+yMhhwptYmIi\n9Ai1yaWVzrTQGbndu3v+OFDZ9/ncRfvyx8nk9PJHs9lMvvG4XFrpTAudCeh6n4rmPfdo73nntY8n\n+j4Vp/PyB0sFAABYl8U1FQAAYGdjqQAAAJVgqYhc/33QKcullc600JmWXDrLYqmIXLO5pZe7opZL\nK51poTMtuXSWxYWaAABgHRdqAgCA4FgqAABAJVgqAABAJVgqIrfRb8dLVS6tdKaFzrTk0lkWS0Xk\nDh48GHqE2uTSSmda6ExLLp1lcfcHAABYx90fAAAgOJYKAABQCZaKyC0sLIQeoTa5tNKZFjrTkktn\nWSwVkWs0GqFHqE0urXSmhc605NJZFhdqAgCAdVyoCQAAgmOpAAAAlWCpAAAAlWCpiNz4+HjoEWqT\nSyudaaEzLbl0lsVSEbmRkZHQI9Qml1Y600JnWnLpLIu7PwAAwDru/gAAAMFFsVSY2Rlm9joz+6KZ\ntczs82b2mtBzAQCA74liqZD0akm/KunXJf2YpEOSDplZ9r+DdmlpKfQItcmllc600JmWXDrLimWp\nGJb0AXf/sLuvuvufSFqU9PzAcwV35MiR0CPUJpdWOtNCZ1py6Swrigs1zex6Sb8i6RJ3/3szu1DS\nhyVNuft7N/j6bC7UbLVa2rVrV+gxapFLK51poTMtOXSezoWaZ27PSJV7g6QflLRiZo+ofYblho0W\nityk/s3dLZdWOtNCZ1py6Swrlpc/xiRdLelKSc+R9EuSps3sF072oNHRURVF0fMxPDw88KtrFxcX\nVRTFwOMnJyc1Pz/fc6zZbKooCq2trfUcn5mZ0ezsbM+x1dVVFUWhlZWVnuNzc3Oanp7uOdZqtVQU\nxcDrdY1GY8M3WxkbG6ODDjrooIOO0+poNBrrPxuHhoZUFIWmpqYGHrNZsbz8sSrp9e7+1q5jN0ja\n7+7P3uDrs3n5AwCAKuXwPhW7JD3Sd+xRxTP/tunfWFOWSyudaaEzLbl0lhXLNRW3SnqNmf2DpL+V\ntFfSlKS3B51qB9izZ0/oEWqTSyudaaEzLbl0lhXLyx9nS3qdpFdI2i3pq5LeI+l17v7dDb6elz8A\nACgh+bs/3P1hSb/R+QAAADtQ9tckAACAarBURK7/dqOU5dJKZ1roTEsunWWxVETu0KFDoUeoTS6t\ndKaFzrTk0llWFBdqblVOF2qurq5mczVyLq10poXOtOTQmcP7VOAEUv/m7pZLK51poTMtuXSWxVIB\nAAAqwVIBAAAqwVIRuf5fQpOyXFrpTAudacmlsyyWisi1Wq3QI9Qml1Y600JnWnLpLIu7PwAAwDru\n/gAAAMGxVAAAgEqwVERubW0t9Ai1yaWVzrTQmZZcOstiqYjcxMRE6BFqk0srnWmhMy25dJbFUhG5\nw4cPhx6hNrm00pkWOtOSS2dZ3P0BAADWcfcHAAAIjqUCAABUgqUicvPz86FHqE0urXSmhc605NJZ\nFktF5JrNLb3cFbVcWulMC51pyaWzLC7UBAAA67hQEwAABMdSAQAAKhHFUmFm95jZoxt8zIWeDQAA\ntEWxVEh6rqShro99klzS+0IOtRMURRF6hNrk0kpnWuhMSy6dZZ0ZeoDNcPcHu/9sZpdJ+oK7/2Wg\nkXaMgwcPhh6hNrm00pkWOtOSS2dZ0d39YWaPlfRVSf/V3WdP8DXc/QEAQAm53f3xCknnSHpn6EEA\nAMD3xLhUTEj6kLvfF3oQAADwPVEtFWa2R9LLJL1tM18/Ojqqoih6PoaHh7WwsNDzdYuLixtefDM5\nOTnwlqzNZlNFUWhtba3n+MzMjGZne1+NWV1dVVEUWllZ6Tk+Nzen6enpnmOtVktFUWhpaanneKPR\n0Pj4+MBsY2NjWlhY6GmJuaPbiTouvfTSJDpO9Xx0/z0xd3TbqONtb3tbEh2nej6654i5o9tGHQsL\nC0l0SCd/Pq6//vokOo4/H41GY/1n49DQkIqi0NTU1MBjNs3do/mQdFjSvZLOOMXX7ZXky8vLnror\nrrgi9Ai1yaWVzrTQmZYcOpeXl13tOyz3+hZ/TkdzoaaZmaR7JN3i7jec4mu5UBMAgBJyuVDzZZLO\nlfRHoQcBAACDonifCkly92OSHhN6DgAAsLGYzlQAAIAdjKUichtd2ZuqXFrpTAudacmlsyyWisiN\njIyEHqE2ubTSmRY605JLZ1nR3P2xFdz9AQBAObnc/QEAAHYwlgoAAFAJlorI9b8ta8pyaaUzLXSm\nJZfOslgqInfkyJHQI9Qml1Y600JnWnLpLIsLNSPXarW0a9eu0GPUIpdWOtNCZ1py6ORCzYyl/s3d\nLZdWOtNCZ1py6SyLpQIAAFSCpQIAAFSCpSJy09PToUeoTS6tdKaFzrTk0lkWS0Xk9uzZE3qE2uTS\nSmda6ExLLp1lcfcHAABYx90fAAAgOJYKAABQCZaKyK2srIQeoTa5tNKZFjrTkktnWSwVkTt06FDo\nEWqTSyudaaEzLbl0lsWFmpFbXV3N5mrkXFrpTAudacmhkws1M5b6N3e3XFrpTAudacmlsyyWCgAA\nUAmWCgAAUAmWisjNzs6GHqE2ubTSmRY605JLZ1nRLBVm9hQze7eZrZlZy8zu7FyQmbVWqxV6hNrk\n0kpnWuhMSy6dZUVx94eZPV7SpyV9TNJbJa1JeqakL7j7PRt8fTZ3fwAAUKXTufvjzO0ZqXKvlrTq\n7td0HftyqGEAAMCgWF7+uEzSHWb2PjO738yaZnbNKR8FAABqE8tS8XRJvybp7ySNqP0SyB+Y2S8E\nnWoHWFtbCz1CbXJppTMtdKYll86yYlkqzpC07O6vdfc73f1tkt4m6dqTPWh0dFRFUfR8DA8Pa2Fh\noefrFhcXVRTFwOMnJyc1Pz/fc6zZbKooioFvrJmZmYGrgldXV1UUxcB7xc/NzWl6errnWKvVUlEU\nWlpa6jneaDQ0Pj4+MNvY2JgWFhY0MTGRREe3E3U873nPS6LjVM9H93Mac0e3jTquvPLKJDpO9Xx0\nP58xd3TbqGNiYiKJDunkz8ell16aRMfx56PRaKz/bBwaGlJRFJqamhp4zGbFcqHmlyQtuvsru45d\nK+kGdz93g6/P5kLNZrOZfONxubTSmRY605JDZw5v0/1xSc/qO/YscbFm8t/c3XJppTMtdKYll86y\nYlkq3iTpBWZ2vZn9GzO7WtI1km4OPBcAAOiIYqlw9zskvULSVZL+RtINkl7l7u8NOhgAAFgXxVIh\nSe7+p+7+k+6+y91/3N3/MPRMO0H/hUApy6WVzrTQmZZcOsuKZqnAxprNLV1DE7VcWulMC51pyaWz\nrCju/tiqnO7+AACgSjnc/QEAAHY4lgoAAFAJlgoAAFAJlorIbfT2sKnKpZXOtNCZllw6y2KpiNzB\ngwdDj1CbXFrpTAudacmlsyzu/gAAAOu4+wMAAAS35aXCzN5pZi/ejmEAAEC8ypypOEfSR83s783s\nP5vZD1c9FDZvYWEh9Ai1yaWVzrTQmZZcOsva8lLh7i+X9MOS3ippTNKXzOxDZvbzZvbYqgfEyTUa\njdAj1CaXVjrTQmdacuks67Qv1OxcFDmu9q8i/2dJRyW9xd3//vTHO62ZuFATAIAtCnahppk9WdK+\nzscjkv5U0k9IusvMpk7n7wYAAHEpc6HmY83s35vZ/5L0ZUn/QdJNkp7i7r/k7i+TdIWk3652VAAA\nsJOdWeIxX1N7GWlIer67f2aDr/kzSf94OoMBAIC4lHn5Y0rtsxKTJ1go5O7/6O7nnd5o2Izx8fHQ\nI9Qml1Y600JnWnLpLGvLZyrc/d3bMQjKGRkZCT1CbXJppTMtdKYll86yeJtuAACwjrfpBgAAwbFU\nAACASrBURG5paSn0CLXJpZXOtNCZllw6y2KpiNyRI0dCj1CbXFrpTAudacmls6woLtQ0sxlJM32H\nV9z92Sf4+mwu1Gy1Wtq1a1foMWqRSyudaaEzLTl0ns6FmmXe/CqUz0p6qSTr/Pm7AWfZMVL/5u6W\nSyudaaEzLbl0lhXTUvFdd/966CGAbXHsmPTAA4PHd++W9u2rfx4AKCGmpeKZZnavpG9J+qSk6939\nK4FnAk7fsWPSyd5QZ3GRxQJAFGK5UPNTkn5Z0iWSrpV0nqS/MLOzQw61E0xPT4ceoTbJtvadoRio\n3OgMRgKSfT770JmWXDrLiuJMhbt/pOuPnzWz29X+DalXSPqjMFPtDHv27Ak9Qm1yac2jMqPnk86k\n5NJZVixnKnq4+0OSPifpGSf7utHRURVF0fMxPDyshYWFnq9bXFxUURQDj5+cnNT8/HzPsWazqaIo\ntLa21nN8ZmZGs7OzPcdWV1dVFIVWVlZ6js/NzQ1su61WS0VRDNwD3Wg0NvwFNmNjY1pYWNB1112X\nREe3E3WsrKwk0bHh8yGpkLQm6bqu4zOSZm+9NZ6OLTwfl19+eRIdp3o+uv9/NOaObht1XHfddUl0\nSCd/Ps4999wkOo4/H41GY/1n49DQkIqi0NTU1MBjNiuKW0r7mdnjJK1K+m13v3mDz2dzSykScMst\n0oEDJ/780aPS/v31zQMga8n/7g8ze6OZvdjMfsTMXijp/ZK+I6kReDQAANARxVIh6amS3iNpRdJ7\nJX1d0gvc/cGgU+0A/afGUpZs6+7dPX8cqOz7fCqSfT770JmWXDrLimKpcPer3P2p7v4D7r7H3a92\n93tCz7UTHDp0KPQItUm2dd++9m2jR49KR4/q0HOes/6/p3w7abLPZx8605JLZ1lRXlNxKjldU7G6\nuprN1ci5tNKZFjrTkkNn8tdU4MRS/+bulksrnWmhMy25dJbFUgEAACrBUgEAACrBUhG5/jdMSVku\nrXSmhc605NJZFktF5FqtVugRapNLK51poTMtuXSWxd0fAABgHXd/AACA4FgqAABAJVgqItf/2+5S\nlksrnWmhMy25dJbFUhG5iYmJ0CPUJpdWOtNCZ1py6SyLpSJyhw8fDj1CbXJppTMtdKYll86yuPsD\nAACs4+4PAAAQHEsFAACoBEtF5Obn50OPUJtcWulMC51pyaWzLJaKyDWbW3q5K2q5tNKZFjrTkktn\nWVyoCQAA1nGhJgAACI6lAgAAVIKlAgAAVIKlInJFUYQeoTa5tNKZFjrTkktnWSwVkTt48GDoEWqT\nSyudaaEzLbl0lsXdHwAAYF12d3+Y2avN7FEz+/3QswAAgLYzQw+wVWb2PEmvlHRn6FkAYEPHjkkP\nPDB4fPduad+++ucBahLVmQoze5yko5KukfSPgcfZERYWFkKPUJtcWumM3LFj0siIdOCAdOCAFjr/\nUwcOtI8fOxZ6wm2R7PPZJ5fOsqJaKiS9WdKt7n5b6EF2ikajEXqE2uTSSmfk+s5QDFRudAYjAck+\nn31y6Swrmpc/zOxKST8l6bmhZ9lJ/viP/zj0CLXJpZXOtORRmdHzmUlnWVGcqTCzp0q6SdJ+d//O\nZh83Ojqqoih6PoaHhwdOXy0uLm547/Hk5OTAb6RrNpsqikJra2s9x2dmZjQ7O9tzbHV1VUVRaGVl\npef43Nycpqene461Wi0VRaGlpaWe441GQ+Pj4wOzjY2N0UEHHTu5Q1JvhdSSVNx4Y1wdqTwfdGzY\n0Wg01n82Dg0NqSgKTU1NDTxms6K4pdTMLpf0J5IekWSdw4+R5J1j3+9dIdxSCiCYW25pXz9xIkeP\nSvv31zcPsEWnc0tpLC9/fFTST/Qde4ekuyW9wWPYjAAASFwUL3+4+8Puflf3h6SHJT3o7neHni+k\njU5tpSqXVjojt3t3zx8HKvs+n4pkn88+uXSWFcuZio1wdkLSyMhI6BFqk0srnZHbt09aXFy/y2Pk\nE5+QXvjC9ucSfp+KZJ/PPrl0lhXFNRVbxTUVAACUk93bdAMAgJ2HpQIAAFSCpSJy/fclpyyXVjrT\nQmdacuksi6UickeOHAk9Qm1yaaUzLXSmJZfOsrhQM3KtVku7du0KPUYtcmmlMy10piWHTi7UzFjq\n39zdcmmlMy10piWXzrJYKgAAQCVYKgAAQCVYKiLX/9vqUpZLK51poTMtuXSWxVIRuT179oQeoTa5\ntNKZFjrTkktnWdz9AQAA1nH3BwAACI6lAgAAVIKlInIrKyuhR6hNLq10poXOtOTSWRZLReQOHToU\neoTa5NJKZ1roTEsunWVxoWbkVldXs7kaOZdWOtNCZ1py6ORCzYyl/s3dLZdWOtNCZ1py6SyLpQIA\nAFSCpQIAAFSCpSJys7OzoUeoTS6tdKaFzrTk0lkWS0XkWq1W6BFqk0srnWmhMy25dJbF3R8AAGAd\nd38AAIDgolgqzOxaM7vTzB7qfHzCzH429FwAAOB7olgqJH1F0m9J2ivpIkm3SfqAmZ0fdKodYG1t\nLfQItcmllc600JmWXDrLimKpcPf/7e4fdvcvuPvn3f01kv5Z0gtCzxbaxMRE6BFqk0srnWmhMy25\ndJZ1ZugBtsrMzpB0haRdkj4ZeJzgDh8+HHqE2uTSSmda6ExLLp1lRXP3h5ldoPYScZakf5J0tbt/\n+ARfy90fAACUkMvdHyuSLpT0fElvlfQuM/uxsCMBAIDjolkq3P277v5Fd/+0u98g6U5JrzrZY0ZH\nR1UURc/H8PCwFhYWer5ucXFRRVEMPH5yclLz8/M9x5rNpoqiGLhYZ2ZmZuCd1lZXV1UUhVZWVnqO\nz83NaXp6uudYq9VSURRaWlrqOd5oNDQ+Pj4w29jYGB100EEHHXScVkej0Vj/2Tg0NKSiKDQ1NTXw\nmE1z9yg/JH1M0h+e4HN7Jfny8rKn7u1vf3voEWqTSyudaaEzLTl0Li8vuySXtNe3+LM5ijMVZvZ7\nZvYiM/sRM7vAzF4v6WJJR0PPFlqzuaWXu6KWSyudaaEzLbl0lhXFhZpm9nZJ/07SkyU9JOmvJb3B\n3W87wddzoSYAACWczoWaUdxS6u7XhJ4BAACcXBQvfwAAgJ2PpQIAAFSCpSJyG93KlKpcWulMC51p\nyaWzLJaKyB08eDD0CLXJpZXOtNCZllw6y4ri7o+t4u4PAADKyeVtugEAwA7GUgEAACrBUhG5/veh\nT1kurXSmhc605NJZFktF5BqNRugRapNLK51poTMtuXSWxYWaAABgHRdqAgCA4FgqAABAJVgqAABA\nJVgqIjc+Ph56hNrk0kpnWuhMSy6dZbFURG5kZCT0CLXJpZXOtNCZllw6y+LuDwAAsI67PwAAQHAs\nFQAAoBIsFZFbWloKPUJtcmmlMy10piWXzrJYKiJ35MiR0CPUJpdWOtNCZ1py6SyLCzUj12q1tGvX\nrtBj1CKXVjrTQmdacujkQs2Mpf7N3S2XVjrTQmdacuksi6UCAABUgqUCAABUIoqlwsyuN7Pbzeyb\nZna/mb3fzH409Fw7wfT0dOgRapNLK51poTMtuXSWdWboATbpRZLmJN2h9syvl7RoZue7+78EnSyE\nY8ekBx6QJO154AHpllvax3fvlvbtCzjY9tqzZ0/oEWpBZ1roTEsunWVFefeHmT1B0gOSXuzuAzcN\nJ333x7Fj0snee35xMenFAgCwvXK8++PxklzSN0IPUrvOGYrSnwcAYJtEt1SYmUm6SdKSu98Veh4A\nANAW3VIh6S2Sni3pylN94ejoqIqi6PkYHh7WwsJCz9ctLi6qKIqBx09OTmp+fr7nWLPZVFEUWltb\n6zk+MzOj2dnZnmOrq6sqikIrKys9x+fm5gYu9mm1WiqKYuAtYBuNhsbHxwdmG5O0IKn7b16UVNx4\nY1wdY2Obfj6uvvrqJDpO9Xx0zxdzR7eNOm677bYkOk71fHQfj7mj20YdKysrSXRIJ38+br755iQ6\njj8fjUZj/Wfj0NCQiqLQ1NTUwGM2zd2j+ZB0s6QvS9pziq/bK8mXl5c9OUePukvrH5d1/e8utT+f\nqMsuuyz0CLWgMy10piWHzuXlZVf7EoO9vsWf07Hc/SEzu1nS5ZIudvfV0PPsFDef+kuS0f8vhFTR\nmRY605JLZ1lRLBVm9hZJV0kqJD1sZk/qfOohd/9WuMkC2L27548DNzf1fT4ludzKRWda6ExLLp1l\nRbFUSLpW7VMxf953fFzSu2qfJqR9+9q3jW50l0fi71MBANjZolgq3D3GC0q3D4sDAGAH4od15Pqv\nGE5ZLq10poXOtOTSWRZLReRarVboEWqTSyudaaEzLbl0lhXl23SfStJv0w0AwDbK8W26AQDADsNS\nAQAAKsFSEbn+t3tNWS6tdKaFzrTk0lkWS0XkJiYmQo9Qm1xa6UwLnWnJpbMslorIHT58OPQItcml\nlc600JmWXDrL4u4PAACwjrs/AABAcCwVAACgEiwVkZufnw89Qm1yaaUzLXSmJZfOslgqItdsbunl\nrqjl0kpnWuhMSy6dZXGhJgAAWMeFmgAAIDiWCgAAUAmWCgAAUAmWisgVRRF6hNrk0kpnWuhMSy6d\nZbFURO7gwYOhR6hNLq10poXOtOTSWRZ3fwAAgHXc/QEAAIJjqQAAAJVgqYjcwsJC6BFqk0srnWmh\nMy25dJYVxVJhZi8ysw+a2b1m9qiZcfltx+zsbOgRapNLK51poTMtuXSWFcVSIelsSZ+R9OuS0ruy\n9DQ88YlPDD1CbXJppTMtdKYll86yzgw9wGa4+4clfViSzMwCjwMAADYQy5kKAACww7FUAACASkTx\n8kcJZ0nS3XffHXqObXf77ber2dzSe5NEK5dWOtNCZ1py6Oz62XnWVh8b3Ttqmtmjkl7u7h88yddc\nLemW+qYCACA5+939PVt5QKpnKj4iab+kL0n6VthRAACIylmSnqb2z9ItieJMhZmdLekZkkxSU9Jv\nSPozSd9w96+EnA0AALTFslRcrPYS0T/sO919IsBIAACgTxRLBQAA2Pm4pRQAAFSCpQIAAFQiyaXC\nzCbN7B5QGPkYAAAGl0lEQVQz+xcz+5SZPS/0TFXL4Zesmdn1Zna7mX3TzO43s/eb2Y+GnqtqZnat\nmd1pZg91Pj5hZj8beq7tZmav7nzv/n7oWapmZjOdtu6Pu0LPtR3M7Clm9m4zWzOzVud7eW/ouarU\n+XnS/3w+amZzoWerkpmdYWavM7Mvdp7Lz5vZa7bydyS3VJjZmKQbJc1Ieo6kOyV9xMyeEHSw6uXw\nS9ZeJGlO0k9Lepmkx0paNLMfCDpV9b4i6bck7ZV0kaTbJH3AzM4POtU26iz6r1T7/z9T9VlJT5I0\n1Pn4mbDjVM/MHi/p45K+LekSSedL+k+S/m/IubbBc/W953FI0j61/7v7vpBDbYNXS/pVtX+u/Jik\nQ5IOmdnBzf4FyV2oaWafkvRX7v6qzp9N7f9o/4G7Hwk63DbZzBuCpaCzGD4g6cXuvhR6nu1kZg9K\n+k13/6PQs1TNzB4naVnSr0l6raRPu/tvhJ2qWmY2I+lyd0/qX+z9zOwNkobd/eLQs9TJzG6SNOru\nSZ05NbNbJd3n7r/Sdex/Smq5+y9u5u9I6kyFmT1W7X/pfez4MW9vTR+VNBxqLlTm8Wr/6+AboQfZ\nLp3Tj1dK2iXpk6Hn2SZvlnSru98WepBt9szOy5NfMLOjZnZu6IG2wWWS7jCz93Veomya2TWhh9pO\nnZ8z+yXNh55lG3xC0kvN7JmSZGYXSvq3kv50s39Bau+o+QRJj5F0f9/x+yU9q/5xUJXOGaebJC25\ne3KvTZvZBWovEWdJ+idJr3D3lbBTVa+zMP2U2qeTU/YpSb8s6e8kPVnSYUl/YWYXuPvDAeeq2tPV\nPuN0o6T/Iun5kv7AzL7t7u8OOtn2eYWkcyS9M/Qg2+ANkn5Q0oqZPaL2iYcb3P29m/0LUlsqkK63\nSHq22ltzilYkXaj2f6x+XtK7zOzFKS0WZvZUtRfDl7n7d0LPs53cvfvtjT9rZrdL+rKkKySl9JLW\nGZJud/fXdv58Z2dBvlZSqkvFhKQPuft9oQfZBmOSrpZ0paS71P4HwH8zs69udklMbalYk/SI2hdH\ndXuSpBS/AbJgZjdLGpX0Inf/Wuh5toO7f1fSFzt//LSZPV/Sq9T+V2AqLpL0REnNzpknqX1m8cWd\nC8G+31O7yKvD3R8ys8+p/esGUvI1Sf2/DvpuST8XYJZtZ2Z71L5o/OWhZ9kmRyS93t3/R+fPf2tm\nT5N0vTa5JCZ1TUXnXz/Lkl56/FjnP14vVfu1IkSms1BcLukl7r4aep4anSHp+0MPUbGPSvoJtf/1\nc2Hn4w5JRyVdmOpCIa1fnPoMtX8Ip+TjGnxp+Vlqn5VJ0YTaL6dv+hqDyOxS+x/m3R7VFnaF1M5U\nSNLvS3qHmS1Lul3SlNr/h3pHyKGq1vdL1iTp6Z2LapL5JWtm9hZJV0kqJD1sZsfPQD3k7sn89lkz\n+z1JH5K0KulfqX0R2MWSRkLOVbXOtQQ918OY2cOSHnT3/n/tRs3M3ijpVrV/uP6wpN+R9B1JjZBz\nbYM3Sfq4mV2v9u2VPy3pGkm/ctJHRajzD9RflvQOd3808Djb5VZJrzGzf5D0t2rf5j4l6e2b/QuS\nWyrc/X2dWw9/V+2XPT4j6RJ3/3rYySr3XH3vl6y52hdKSe2Lh1L5JWvXqt32533HxyW9q/Zpts9u\ntZ+3J0t6SNJfSxrJ4O4IKd33WHmqpPdI+iFJX5e0JOkF7v5g0Kkq5u53mNkr1L7A77WS7pH0qq1c\n2BeRl0k6V2ldE9PvoKTXqX2H1m5JX5X01s6xTUnufSoAAEAYSV1TAQAAwmGpAAAAlWCpAAAAlWCp\nAAAAlWCpAAAAlWCpAAAAlWCpAAAAlWCpAAAAlWCpAAAAlWCpAAAAlWCpAAAAlWCpAAAAlWCpAFAL\nM3uCmX3NzF7ddeyFZvZtM3tJyNkAVIPfUgqgNmZ2qaQFScOSPifpM5Le7+7TQQcDUAmWCgC1MrM5\nSfsk3SHpAknPc/fvhJ0KQBVYKgDUyszOkvRZSU+VtNfd7wo8EoCKcE0FgLo9Q9JT1P7vz3mBZwFQ\nIc5UAKiNmT1W0u2SPi3p7yRNSbrA3deCDgagEiwVAGpjZm+U9HOSflJSS9KfS/qmu18Wci4A1eDl\nDwC1MLOLJf1HSQfc/WFv/4vmFyX9jJn9atjpAFSBMxUAAKASnKkAAACVYKkAAACVYKkAAACVYKkA\nAACVYKkAAACVYKkAAACVYKkAAACVYKkAAACVYKkAAACVYKkAAACVYKkAAACV+P8wtsdw4zP7HQAA\nAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1061a6590>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Задача 5\n",
    "\n",
    "Оцените вычислительную сложность предсказания с помощью метода $k$-NN по данным с $N$ объектами и $D$ признаками"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  },
  "nav_menu": {},
  "toc": {
   "navigate_menu": true,
   "number_sections": false,
   "sideBar": true,
   "threshold": 6,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}