book_learning_2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 《Problem Solving with Algorithms and Data Structures using Python》 的学习笔记和课后作业答案（二. Analysis） \n",
    "\n",
    "```\n",
    "对应本书第二章。\n",
    "```\n",
    "\n",
    "## 目录\n",
    "\n",
    "* [2.Analysis](#2.Analysis)\n",
    "    + [笔记](#笔记)\n",
    "        + [一. 大O](#一.-大O)\n",
    "        + [二. List](#二.-List)\n",
    "        + [三. Dictionary](#三.-Dictionary)\n",
    "    + [作业](#作业)\n",
    "        + [q1 证明list的index操作是O(1)](#q1)\n",
    "        + [q2 证明dict的get和set是O(1)](#q1)\n",
    "        + [q3 对比list和dict的del操作](#q3)\n",
    "        + [q4 给定一个list，返回第k小的数，O(nlogn)](#q4)\n",
    "        + [q5 q4时间复杂度是O(n)的解法](#q5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2.Analysis\n",
    "\n",
    "## 笔记\n",
    "\n",
    "这章主要讲了算法复杂度的分析。\n",
    "\n",
    "### 一. 大O\n",
    "    \n",
    "名称源自于**Order of magnitude function $O(f(n))$** 描述了时间复杂度**$T(n)$**当中**增长速度最快**的部分。 \n",
    "\n",
    "例如：$T(n)=5n^2+27n+1005$的阶是$O(n^2)$。\n",
    "\n",
    "因为不同的机器计算速度的区别，和不同的编程语言的效率的不同，所以分析算法的时间复杂度使用这样的粗粒度就足够了。\n",
    "\n",
    "不同函数的增长速度：\n",
    "    \n",
    "![](https://raw.githubusercontent.com/applenob/algorithm_note/master/res/plot.png)\n",
    "\n",
    "python自带的数据结构：\n",
    "\n",
    "### 二. List\n",
    "\n",
    "|Operation\t|Big-O Efficiency|\n",
    "|:-----------:|:----------------:|\n",
    "|index []\t|O(1)|\n",
    "|index assignment\t|O(1)|\n",
    "|append\t|O(1)|\n",
    "|pop()\t|O(1)|\n",
    "|pop(i)\t|O(n)|\n",
    "|insert(i,item)\t|O(n)|\n",
    "|del operator\t|O(n)|\n",
    "|iteration\t|O(n)|\n",
    "|contains (in)\t|O(n)|\n",
    "|get slice [x:y]\t|O(k)|\n",
    "|del slice\t|O(n)|\n",
    "|set slice\t|O(n+k)|\n",
    "|reverse\t|O(n)|\n",
    "|concatenate\t|O(k)|\n",
    "|sort\t|O(n log n)|\n",
    "|multiply\t|O(nk)|\n",
    "\n",
    "其中，需要注意的是concatenate还有pop和pop(i)的区别。\n",
    "\n",
    "[python 中list的实现](http://www.jianshu.com/p/J4U6rR)\n",
    "\n",
    "![](https://raw.github.com/acmerfight/insight_python/master/images/list_insert.png)\n",
    "\n",
    "### 三. Dictionary\n",
    "\n",
    "\n",
    "|operation\t|Big-O Efficiency|\n",
    "|:-----------:|:----------------:|\n",
    "|copy\t|O(n)|\n",
    "|get item\t|O(1)|\n",
    "|set item\t|O(1)|\n",
    "|delete item\t|O(1)|\n",
    "|contains (in)\t|O(1)|\n",
    "|iteration\t|O(n)|\n",
    "\n",
    "dict的in操作是O(1)，list是O(n)\n",
    "\n",
    "[python的dict实现](http://www.jianshu.com/p/02af9673ab34)\n",
    "\n",
    "## 作业\n",
    "\n",
    "[作业链接](http://interactivepython.org/courselib/static/pythonds/AlgorithmAnalysis/ProgrammingExercises.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q1\n",
    "\n",
    "是证明list的index操作是O(1)。暂且认为list的pop(0)是O(n)是已知条件。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from timeit import Timer\n",
    "# q1\n",
    "def test5():\n",
    "    l = list(range(1000))\n",
    "    for i in range(1000):\n",
    "        l[i] = 1\n",
    "\n",
    "def test6():\n",
    "    l = list(range(1000))\n",
    "    for i in range(1000):\n",
    "        l.pop(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "list index operation: 0.0006067330032237805 milliseconds\n",
      "list pop(0): 0.0025059110048459843 milliseconds\n"
     ]
    }
   ],
   "source": [
    "t5 = Timer(\"test5()\", \"from __main__ import test5\")\n",
    "print(\"list index operation:\",t5.timeit(number=10), \"milliseconds\")\n",
    "t6 = Timer(\"test6()\", \"from __main__ import test6\")\n",
    "print(\"list pop(0):\",t6.timeit(number=10), \"milliseconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q2\n",
    "\n",
    "是证明dict的get和set是O(1)，先认为dict的遍历是O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def test7():\n",
    "    d = dict(zip(list(range(1000)), list(range(1000,2000))))\n",
    "    for i in range(1000):\n",
    "        d[i] = 1\n",
    "\n",
    "def test8():\n",
    "    d = dict(zip(list(range(1000)), list(range(1000,2000))))\n",
    "    for i in range(1000):\n",
    "        k = d[i]\n",
    "        \n",
    "def test9():\n",
    "    d = dict(zip(list(range(1000)), list(range(1000,2000))))\n",
    "    for i in range(1000):\n",
    "        for one in d:\n",
    "            pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dict set item: 0.13327282800310059 milliseconds\n",
      "dict get item: 0.1195711559994379 milliseconds\n",
      "dict iteration: 11.517200201000378 milliseconds\n"
     ]
    }
   ],
   "source": [
    "t7 = Timer(\"test7()\", \"from __main__ import test7\")\n",
    "print(\"dict set item:\",t7.timeit(number=1000), \"milliseconds\")\n",
    "t8 = Timer(\"test8()\", \"from __main__ import test8\")\n",
    "print(\"dict get item:\",t8.timeit(number=1000), \"milliseconds\")\n",
    "t9 = Timer(\"test9()\", \"from __main__ import test9\")\n",
    "print(\"dict iteration:\",t9.timeit(number=1000), \"milliseconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q3\n",
    "\n",
    "对比list和dict的del操作"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def test10():\n",
    "    l = list(range(1000))\n",
    "    for i in range(1000):\n",
    "        del l[0]\n",
    "        \n",
    "def test11():\n",
    "    d = dict(zip(list(range(1000)), list(range(1000,2000))))\n",
    "    for i in range(1000):\n",
    "        del d[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "list del item: 0.14648991199646844 milliseconds\n",
      "dict del item: 0.13190877300075954 milliseconds\n",
      "list del item: 0.14080390099843498 milliseconds\n",
      "dict del item: 0.13055396499839844 milliseconds\n"
     ]
    }
   ],
   "source": [
    "t10 = Timer(\"test10()\", \"from __main__ import test10\")\n",
    "print(\"list del item:\",t10.timeit(number=1000), \"milliseconds\")\n",
    "t11 = Timer(\"test11()\", \"from __main__ import test11\")\n",
    "print(\"dict del item:\",t11.timeit(number=1000), \"milliseconds\")\n",
    "t10 = Timer(\"test10()\", \"from __main__ import test10\")\n",
    "print(\"list del item:\",t10.timeit(number=1000), \"milliseconds\")\n",
    "t11 = Timer(\"test11()\", \"from __main__ import test11\")\n",
    "print(\"dict del item:\",t11.timeit(number=1000), \"milliseconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q4\n",
    "\n",
    "给定一个list，返回第k小的数。先给出时间复杂度是O(nlogn)的简单版："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def kth_smallest_1(nums, k):\n",
    "    \"\"\"\n",
    "    find kth smallest of a list, O(nlogn)\n",
    "    :type nums: list\n",
    "    :type k: int\n",
    "    :rtype: num\n",
    "    \"\"\"\n",
    "    nums.sort()\n",
    "    return nums[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kth_smallest_1([1, 5,9,10,2,3], 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### q5\n",
    "\n",
    "q4时间复杂度是O(n)的解法。利用快排的思路。平均时间复杂度是O(n)，最坏情况时间复杂度是$O(n^2)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def kth_smallest_2(nums, k):\n",
    "    \"\"\"\n",
    "    find kth smallest of a list, O(n)\n",
    "    :type nums: list\n",
    "    :type k: int\n",
    "    :rtype: num\n",
    "    \"\"\"\n",
    "    def partition(nums, start, end):\n",
    "        \"\"\"\n",
    "        Pick last element as pivot\n",
    "        Place all smaller elements before pivot\n",
    "        Place all bigger elements after pivot\n",
    "        \"\"\"\n",
    "        pivot = nums[end]\n",
    "        # currentSmaller 记录当前有几个数比pivot小\n",
    "        currentSmaller = start\n",
    "        for i in range(start, end):\n",
    "            # If current element <= pivot, put it to right position\n",
    "            if nums[i] <= pivot:\n",
    "                nums[i], nums[currentSmaller] = nums[currentSmaller], nums[i]\n",
    "                currentSmaller += 1\n",
    "        # Put pivot to right position\n",
    "        nums[end], nums[currentSmaller] = nums[currentSmaller], nums[end]\n",
    "        return currentSmaller\n",
    "\n",
    "    def quickSelect(nums, start, end, k):\n",
    "        pos = partition(nums, start, end)\n",
    "        # print(nums)\n",
    "        if pos == k - 1:\n",
    "            return nums[pos]\n",
    "        if pos < k - 1:\n",
    "            return quickSelect(nums, pos + 1, end, k)\n",
    "        else:\n",
    "            return quickSelect(nums, start, pos - 1, k)\n",
    "    return quickSelect(nums, 0, len(nums)-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kth_smallest_2([1,5,9,10,2,3], 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "kth_smallest_1: 7.706003088969737e-06 milliseconds\n",
      "kth_smallest_2: 4.322700260672718e-05 milliseconds\n"
     ]
    }
   ],
   "source": [
    "t12 = Timer(\"kth_smallest_1([1, 5,9,10,2,3], 4)\", \"from __main__ import kth_smallest_1\")\n",
    "print(\"kth_smallest_1:\",t12.timeit(number=10), \"milliseconds\")\n",
    "t13 = Timer(\"kth_smallest_2([1,5,9,10,2,3], 4)\", \"from __main__ import kth_smallest_2\")\n",
    "print(\"kth_smallest_2:\",t13.timeit(number=10), \"milliseconds\")"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:py35]",
   "language": "python",
   "name": "conda-env-py35-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}