Last active
March 30, 2022 18:18
-
-
Save sanchezcarlosjr/3788a69e1144ca9d6105608b08433d1b to your computer and use it in GitHub Desktop.
UABC Unidad 1 - Herramientas de Análisis de Algoritmos.ipynb.ipynb
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"nbformat": 4, | |
"nbformat_minor": 0, | |
"metadata": { | |
"colab": { | |
"name": "UABC Unidad 1 - Herramientas de Análisis de Algoritmos.ipynb.ipynb", | |
"provenance": [], | |
"collapsed_sections": [], | |
"include_colab_link": true | |
}, | |
"kernelspec": { | |
"name": "python3", | |
"display_name": "Python 3" | |
}, | |
"language_info": { | |
"name": "python" | |
} | |
}, | |
"cells": [ | |
{ | |
"cell_type": "markdown", | |
"metadata": { | |
"id": "view-in-github", | |
"colab_type": "text" | |
}, | |
"source": [ | |
"<a href=\"https://colab.research.google.com/gist/sanchezcarlosjr/3788a69e1144ca9d6105608b08433d1b/herramientas-de-an-lisis-de-algoritmos.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"source": [ | |
"# 1 Herramientas de Análisis de Algoritmos\n", | |
"## UABC\n", | |
"\n", | |
"### Ilustración\n", | |
"By [Carlos Eduardo Sanchez Torres](https://twitter.com/CharllierJr)\n", | |
"\n", | |
"[Análisis de algoritmos](https://sanchezcarlosjr.notion.site/An-lisis-de-Algoritmos-38fac5ca34e740719b43673db9f8b9188)" | |
], | |
"metadata": { | |
"id": "mRIP_0yy7GHb" | |
} | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"id": "jx85EMoFI6Gb" | |
}, | |
"source": [ | |
"def merge(sequence, i, compareFunction):\n", | |
" key = sequence[i+1]\n", | |
" print(sequence[:i+1])\n", | |
" while i >= 0 and compareFunction(sequence[i], key):\n", | |
" sequence[i+1] = sequence[i]\n", | |
" i = i - 1\n", | |
" sequence[i+1] = key" | |
], | |
"execution_count": null, | |
"outputs": [] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "mYDvHsnplNae", | |
"outputId": "d8dfedc9-40c6-4f53-c24f-285f27f38b2a" | |
}, | |
"source": [ | |
"def insertion_sort(numberSequence, compareFunction):\n", | |
" for j in range(1,len(numberSequence)):\n", | |
" merge(numberSequence, j-1, compareFunction)\n", | |
" return numberSequence\n", | |
"\n", | |
"insertion_sort([4,3,2,1], lambda a,b : a > b)" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"[4]\n", | |
"[3, 4]\n", | |
"[2, 3, 4]\n" | |
] | |
}, | |
{ | |
"output_type": "execute_result", | |
"data": { | |
"text/plain": [ | |
"[1, 2, 3, 4]" | |
] | |
}, | |
"metadata": {}, | |
"execution_count": 220 | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "t04R8W_zlb5v", | |
"outputId": "65164fc6-fdc9-499a-fd12-f7052858dcda" | |
}, | |
"source": [ | |
"insertion_sort([1,2,3,4], lambda a,b : a < b)" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "execute_result", | |
"data": { | |
"text/plain": [ | |
"[4, 3, 2, 1]" | |
] | |
}, | |
"metadata": {}, | |
"execution_count": 132 | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"id": "v5wS5kGorSY_", | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"outputId": "93798384-f502-4161-f374-54de84852636" | |
}, | |
"source": [ | |
"def for_recursive(sequence, j=0):\n", | |
" if j <= len(sequence):\n", | |
" print(sequence[:j])\n", | |
" for_recursive(sequence,j+1)\n", | |
" \n", | |
"for_recursive([1,2,3,4])" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"[]\n", | |
"[1]\n", | |
"[1, 2]\n", | |
"[1, 2, 3]\n", | |
"[1, 2, 3, 4]\n" | |
] | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "lhn5RRXmynLG", | |
"outputId": "aa35de40-0922-47ac-90dd-74eabe2aff93" | |
}, | |
"source": [ | |
"def for_inverse_recursive(sequence, j=0):\n", | |
" if j <= len(sequence):\n", | |
" for_inverse_recursive(sequence,j+1)\n", | |
" print(sequence[:j])\n", | |
"\n", | |
"for_inverse_recursive([1,2,3,4])" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"[1, 2, 3, 4]\n", | |
"[1, 2, 3]\n", | |
"[1, 2]\n", | |
"[1]\n", | |
"[]\n" | |
] | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "S5M9_JTEyu4u", | |
"outputId": "80c0a6d0-6efc-4237-a1fc-abddc0531255" | |
}, | |
"source": [ | |
"def insertion_sort_recursive(sequence, j=1):\n", | |
" if j < len(sequence):\n", | |
" merge(sequence, j-1, lambda a,b: a > b)\n", | |
" insertion_sort_recursive(sequence,j+1)\n", | |
" return sequence\n", | |
"\n", | |
"insertion_sort_recursive([4,3,2,1])" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"[4]\n", | |
"[3, 4]\n", | |
"[2, 3, 4]\n" | |
] | |
}, | |
{ | |
"output_type": "execute_result", | |
"data": { | |
"text/plain": [ | |
"[1, 2, 3, 4]" | |
] | |
}, | |
"metadata": {}, | |
"execution_count": 223 | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "87Hy2rB__wj8", | |
"outputId": "df0cbd8e-9071-42b3-a106-b71d511c11f7" | |
}, | |
"source": [ | |
"def insertion_sort_recursive_stack(sequence, n=-1):\n", | |
" n = len(sequence) if n == -1 else n \n", | |
" if n > 1:\n", | |
" insertion_sort_recursive_stack(sequence, n-1)\n", | |
" merge(sequence, n-2, lambda a,b: a > b)\n", | |
" return sequence\n", | |
"\n", | |
"insertion_sort_recursive_stack([4,3,2,1])\n", | |
"print()\n", | |
"insertion_sort_recursive_stack([1,2,3,4])" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"[4]\n", | |
"[3, 4]\n", | |
"[2, 3, 4]\n", | |
"\n", | |
"[1]\n", | |
"[1, 2]\n", | |
"[1, 2, 3]\n" | |
] | |
}, | |
{ | |
"output_type": "execute_result", | |
"data": { | |
"text/plain": [ | |
"[1, 2, 3, 4]" | |
] | |
}, | |
"metadata": {}, | |
"execution_count": 6 | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"id": "kCb6UDdXIn4A" | |
}, | |
"source": [ | |
"import time\t\t\t\t\t\n", | |
"import numpy as np\n", | |
"from IPython.display import Math\n", | |
"\n", | |
"def timer(f, x):\n", | |
" times = []\n", | |
" for i in range(30):\n", | |
" tic = time.perf_counter()\n", | |
" f(x)\n", | |
" toc = time.perf_counter()\n", | |
" times.append(toc - tic)\n", | |
" print(\"Build finished in \")\n", | |
" output = f\"{np.mean(times):0.4f} \\pm {np.std(times):0.4f} seconds\"\n", | |
" return Math(output)" | |
], | |
"execution_count": null, | |
"outputs": [] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "AL4mEC4aETwU", | |
"outputId": "6623fb9d-9500-4332-e2e5-9c11bf53ae2a" | |
}, | |
"source": [ | |
"def merge(arr,L,R): \n", | |
" i = j = k = 0\n", | |
" while i < len(L) and j < len(R):\n", | |
" if L[i] < R[j]:\n", | |
" arr[k] = L[i]\n", | |
" i += 1\n", | |
" else:\n", | |
" arr[k] = R[j]\n", | |
" j += 1\n", | |
" k += 1\n", | |
" while i < len(L):\n", | |
" arr[k] = L[i]\n", | |
" i += 1\n", | |
" k += 1\n", | |
" while j < len(R):\n", | |
" arr[k] = R[j]\n", | |
" j += 1\n", | |
" k += 1\n", | |
"\n", | |
"def recursiveMergeSort(arr):\n", | |
" if len(arr) > 1:\n", | |
" mid = len(arr)//2\n", | |
" L = arr[:mid]\n", | |
" R = arr[mid:]\n", | |
" recursiveMergeSort(L)\n", | |
" recursiveMergeSort(R)\n", | |
" merge(arr,L,R)\n", | |
" return arr\n", | |
"\n", | |
"timer(recursiveMergeSort, np.random.rand(1,1000000)[0])" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"Build finished in 1.1987 +- 0.0319 seconds\n" | |
] | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "b3rnv4cNE8jl", | |
"outputId": "df61deec-eb9f-489a-a52a-32cefaff833d" | |
}, | |
"source": [ | |
"def mergeSort(a):\n", | |
" # start with least partition size of 2^0 = 1\n", | |
" width = 1 \n", | |
" n = len(a) \n", | |
" # subarray size grows by powers of 2\n", | |
" # since growth of loop condition is exponential,\n", | |
" # time consumed is logarithmic (log2n)\n", | |
" while (width < n):\n", | |
" # always start from leftmost\n", | |
" l=0;\n", | |
" while (l < n):\n", | |
" r = min(l+(width*2-1), n-1)\n", | |
" m = (l+r)//2\n", | |
" # final merge should consider\n", | |
" # unmerged sublist if input arr\n", | |
" # size is not power of 2\n", | |
" if (width>n//2): \n", | |
" m = r-(n%width) \n", | |
" merge(a, l, m, r)\n", | |
" l += width*2\n", | |
" # Increasing sub array size by powers of 2\n", | |
" width *= 2\n", | |
" return a\n", | |
" \n", | |
"# Merge Function\n", | |
"def merge(a, l, m, r):\n", | |
" n1 = m - l + 1\n", | |
" n2 = r - m\n", | |
" L = [0] * n1\n", | |
" R = [0] * n2\n", | |
" for i in range(0, n1):\n", | |
" L[i] = a[l + i]\n", | |
" for i in range(0, n2):\n", | |
" R[i] = a[m + i + 1]\n", | |
" \n", | |
" i, j, k = 0, 0, l\n", | |
" while i < n1 and j < n2:\n", | |
" if L[i] > R[j]:\n", | |
" a[k] = R[j]\n", | |
" j += 1\n", | |
" else:\n", | |
" a[k] = L[i]\n", | |
" i += 1\n", | |
" k += 1\n", | |
" \n", | |
" while i < n1:\n", | |
" a[k] = L[i]\n", | |
" i += 1\n", | |
" k += 1\n", | |
" \n", | |
" while j < n2:\n", | |
" a[k] = R[j]\n", | |
" j += 1\n", | |
" k += 1\n", | |
" \n", | |
"timer(mergeSort, np.random.rand(1,1000000)[0])" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"Build finished in 1.0700 +- 0.0294 seconds\n" | |
] | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "t7Y_Gvq7n9sv", | |
"outputId": "39d47825-f53f-4e79-bb9d-3a966dac6aa4" | |
}, | |
"source": [ | |
"import math \n", | |
"def recursive_binary_search(X,x, p, r): \n", | |
" mid = (p+r)//2\n", | |
" print(X[p:r], end=\",\")\n", | |
" print(X[mid])\n", | |
" if r < p:\n", | |
" return None \n", | |
" if X[mid] == x:\n", | |
" return mid\n", | |
" if X[mid] > x:\n", | |
" return recursive_binary_search(X,x, p, mid-1)\n", | |
" if X[mid] < x:\n", | |
" return recursive_binary_search(X,x, mid+1, r)\n", | |
"\n", | |
"def binary_search(X, x):\n", | |
" if X[-1] < x:\n", | |
" return None \n", | |
" return recursive_binary_search(X, x, 0, len(X))\n", | |
"\n", | |
"assert binary_search([1,2,3,4,5], 1) == 0, \"A[0] == 1\"\n", | |
"print()\n", | |
"assert binary_search([1,2,3,4,5], 5) == 4, \"A[4] == 5\"\n", | |
"print()\n", | |
"assert binary_search([1,2,3,4,5], -1) == None, \"A[] == None\" # Worst case: T(n)=Theta(lg(n))\n", | |
"print()\n", | |
"assert binary_search([1,2,3,4,5], 10) == None, \"A[] == None\"\n", | |
"print()\n", | |
"assert binary_search([1,2,3,4,5], 3) == 2, \"A[] == None\" # Best case: T(n)=O(1)\n", | |
"assert binary_search([1,2,3,4,5,6,7,8], -1) == None, \"A[] == None\" # Worst case: T(n)=Theta(lg(n))\n", | |
"print()" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"[1, 2, 3, 4, 5],3\n", | |
"[1],1\n", | |
"\n", | |
"[1, 2, 3, 4, 5],3\n", | |
"[4, 5],5\n", | |
"\n", | |
"[1, 2, 3, 4, 5],3\n", | |
"[1],1\n", | |
"[1, 2, 3, 4],5\n", | |
"\n", | |
"\n", | |
"[1, 2, 3, 4, 5],3\n", | |
"[1, 2, 3, 4, 5, 6, 7, 8],5\n", | |
"[1, 2, 3],2\n", | |
"[],1\n", | |
"[1, 2, 3, 4, 5, 6, 7],8\n", | |
"\n" | |
] | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "duiQehM92ac7", | |
"outputId": "65a54d23-c3cb-4c6e-c5e1-2df48b192338" | |
}, | |
"source": [ | |
"def binary_search(X, x):\n", | |
" if X[-1] < x:\n", | |
" return None\n", | |
" p = 0\n", | |
" r = len(X)\n", | |
" while p < r:\n", | |
" mid = (p+r)//2\n", | |
" if X[mid] == x:\n", | |
" return mid\n", | |
" if X[mid] < x:\n", | |
" p = mid + 1\n", | |
" if X[mid] > x:\n", | |
" r = mid - 1 \n", | |
" return None\n", | |
"\n", | |
"assert binary_search([1,2,3,4,5], 1) == 0, \"A[0] == 1\"\n", | |
"print()\n", | |
"assert binary_search([1,2,3,4,5], 5) == 4, \"A[4] == 5\"\n", | |
"print()\n", | |
"assert binary_search([1,2,3,4,5], -1) == None, \"A[] == None\" # Worst case: T(n)=Theta(lg(n))\n", | |
"print()\n", | |
"assert binary_search([1,2,3,4,5], 10) == None, \"A[] == None\"\n", | |
"print()\n", | |
"assert binary_search([1,2,3,4,5], 3) == 2, \"A[] == None\" # Best case: T(n)=O(1)\n", | |
"assert binary_search([1,2,3,4,5,6,7,8], -1) == None, \"A[] == None\" # Worst case: T(n)=Theta(lg(n))\n", | |
"print()" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"\n", | |
"\n", | |
"\n", | |
"\n", | |
"\n" | |
] | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "ARIheWUxLt-8", | |
"outputId": "6772735c-27df-4f3f-d734-68670692c747" | |
}, | |
"source": [ | |
"import math\n", | |
"ratio = 1.618033988749895\n", | |
"sqrt5 = 2.2360679775\n", | |
"\n", | |
"def fibonacci_elementA(i):\n", | |
" return math.floor((math.pow(ratio, i)/sqrt5)+0.5)\n", | |
"\n", | |
"def fibonacciA(x):\n", | |
" return [fibonacci_elementA(i) for i in range(x)]\n", | |
"\n", | |
"timer(fibonacciA, 1475)" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"Build finished in 0.0013 +- 0.0012 seconds\n" | |
] | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "Ov83WPCS6Rnt", | |
"outputId": "c8ddb047-a760-41c8-a338-5275b10a9566" | |
}, | |
"source": [ | |
"# T(n)Theta(2^n)\n", | |
"def fibonacci_elementB(n):\n", | |
" return n if n < 2 else fibonacciB(n-1) + fibonacciB(n-2)\n", | |
"\n", | |
"def fibonacciB(x):\n", | |
" return [fibonacci_elementB(i) for i in range(x)]\n", | |
"\n", | |
"timer(fibonacciB, 20)" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"Build finished in 0.1112 +- 0.0353 seconds\n" | |
] | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/", | |
"height": 60 | |
}, | |
"id": "ESDeuHDxGj1L", | |
"outputId": "3a49a967-0b25-4fb2-acab-438c9a0d1f5a" | |
}, | |
"source": [ | |
"from mpmath import *\n", | |
"ratio = 1.618033988749895\n", | |
"sqrt5 = 2.2360679775\n", | |
"\n", | |
"def fibonacci_elementC(i, dps=30):\n", | |
" mp.dps = dps\n", | |
" return floor((power(ratio,i)/sqrt5)+0.5)\n", | |
"\n", | |
"def fibonacciC(x):\n", | |
" return [fibonacci_elementC(i) for i in range(x)]\n", | |
"\n", | |
"timer(fibonacciC, 10000)" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"Build finished in \n" | |
] | |
}, | |
{ | |
"output_type": "execute_result", | |
"data": { | |
"text/latex": "$$0.4638 \\pm 0.0181 seconds$$", | |
"text/plain": [ | |
"<IPython.core.display.Math object>" | |
] | |
}, | |
"metadata": {}, | |
"execution_count": 3 | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "nxdEejgXsLyp", | |
"outputId": "2929482f-d715-4af0-af24-ac01c0ed28a9" | |
}, | |
"source": [ | |
"fibonacci_elementC(10000000)" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "execute_result", | |
"data": { | |
"text/plain": [ | |
"mpf('1.1298343786046051632158517439349e+2089876')" | |
] | |
}, | |
"metadata": {}, | |
"execution_count": 23 | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "uG8PoRkO4Xk0", | |
"outputId": "1e747b18-e32f-443e-b1d3-76f3ac494f4d" | |
}, | |
"source": [ | |
"def fibonacciD(i):\n", | |
" x = [0,1]\n", | |
" for i in range(2,i):\n", | |
" x.append(x[i-2]+x[i-1])\n", | |
" return x\n", | |
"\n", | |
"timer(fibonacciD, 10000)" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"Build finished in 0.0044 +- 0.0008 seconds\n" | |
] | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "HgOGjl1Y8avp", | |
"outputId": "32b38a66-a7b8-4c58-8c87-568eff6877ce" | |
}, | |
"source": [ | |
"timer(fibonacciD, 1475)" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"Build finished in 0.0005 +- 0.0001 seconds\n" | |
] | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"id": "eAjvekpk1Oh6" | |
}, | |
"source": [ | |
"from functools import lru_cache\n", | |
"from mpmath import *\n", | |
"ratio = 1.618033988749895\n", | |
"sqrt5 = 2.2360679775\n", | |
"\n", | |
"# O(1)\n", | |
"@lru_cache(maxsize=32)\n", | |
"def fibonacci(i, dps=30):\n", | |
" mp.dps = dps\n", | |
" return floor((power(ratio,i)/sqrt5)+0.5)\n", | |
"# 0 1 2 3 \n", | |
"# 0 1 1 2 3 5\n", | |
"assert fibonacci(1) == 1, \"F(1)=1\" \n", | |
"assert fibonacci(2) == 1, \"F(2)=1\"\n", | |
"assert fibonacci(3) == 2, \"F(3)=2\"\n", | |
"assert fibonacci(50) == 12586269025, \"F(50)=12586269025\"" | |
], | |
"execution_count": null, | |
"outputs": [] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/", | |
"height": 59 | |
}, | |
"id": "A7E34HYA76Kg", | |
"outputId": "ada97059-d47c-4e72-a63b-356676aba6f4" | |
}, | |
"source": [ | |
"from functools import lru_cache\n", | |
"from mpmath import *\n", | |
"ratio = 1.618033988749895\n", | |
"sqrt5 = 2.2360679775\n", | |
"\n", | |
"# O(1)\n", | |
"@lru_cache(maxsize=32)\n", | |
"def fibonacci_elementE(i, dps=30):\n", | |
" mp.dps = dps\n", | |
" return floor((power(ratio,i)/sqrt5)+0.5)\n", | |
" \n", | |
"@lru_cache(maxsize=32)\n", | |
"def fibonacciE(x):\n", | |
" return [fibonacci_elementE(i) for i in range(x)]\n", | |
"\n", | |
"timer(fibonacciE, 10000)" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"Build finished in \n" | |
] | |
}, | |
{ | |
"output_type": "execute_result", | |
"data": { | |
"text/latex": "$$0.0158 \\pm 0.0851 seconds$$", | |
"text/plain": [ | |
"<IPython.core.display.Math object>" | |
] | |
}, | |
"metadata": {}, | |
"execution_count": 14 | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/", | |
"height": 59 | |
}, | |
"id": "MZQ0q89FFVep", | |
"outputId": "a9fb34cd-a429-479f-88ce-6d08cff0dca5" | |
}, | |
"source": [ | |
"from functools import lru_cache\n", | |
"# T(n)= Theta(n)\n", | |
"# S(n)= Theta(n)\n", | |
"@lru_cache(maxsize=32)\n", | |
"def fibonacciF(n):\n", | |
" x = [0,1]\n", | |
" for i in range(2,n):\n", | |
" x.append(x[i-2]+x[i-1])\n", | |
" return x\n", | |
"\n", | |
"timer(fibonacciF, 10000)" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"Build finished in \n" | |
] | |
}, | |
{ | |
"output_type": "execute_result", | |
"data": { | |
"text/latex": "$$0.0003 \\pm 0.0016 seconds$$", | |
"text/plain": [ | |
"<IPython.core.display.Math object>" | |
] | |
}, | |
"metadata": {}, | |
"execution_count": 15 | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/", | |
"height": 59 | |
}, | |
"id": "Ivf8gl3ATr6g", | |
"outputId": "93509dd2-8029-4aa9-eebe-a23e68435c7a" | |
}, | |
"source": [ | |
"from functools import lru_cache\n", | |
"# T(n)= Theta(n)\n", | |
"# S(n)= Theta(n)\n", | |
"@lru_cache(maxsize=32)\n", | |
"def fibonacciG(n):\n", | |
" x = [0,1]\n", | |
" for i in range(2,n):\n", | |
" x.append(x[i-2]+x[i-1])\n", | |
" return x[n-1]\n", | |
"\n", | |
"timer(fibonacciG, 10000)" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"Build finished in \n" | |
] | |
}, | |
{ | |
"output_type": "execute_result", | |
"data": { | |
"text/latex": "$$0.0004 \\pm 0.0020 seconds$$", | |
"text/plain": [ | |
"<IPython.core.display.Math object>" | |
] | |
}, | |
"metadata": {}, | |
"execution_count": 16 | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/", | |
"height": 59 | |
}, | |
"id": "GmXQ-S4yT5Ft", | |
"outputId": "88d98123-fcb1-497e-c18b-f17fdfd3a6fe" | |
}, | |
"source": [ | |
"timer(fibonacciE, 10000)" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "stream", | |
"name": "stdout", | |
"text": [ | |
"Build finished in \n" | |
] | |
}, | |
{ | |
"output_type": "execute_result", | |
"data": { | |
"text/latex": "$$0.0000 \\pm 0.0000 seconds$$", | |
"text/plain": [ | |
"<IPython.core.display.Math object>" | |
] | |
}, | |
"metadata": {}, | |
"execution_count": 17 | |
} | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"metadata": { | |
"colab": { | |
"base_uri": "https://localhost:8080/" | |
}, | |
"id": "IJX8R5kdUaVh", | |
"outputId": "0ee49101-971d-4c93-ba02-3fc8efad95c6" | |
}, | |
"source": [ | |
"fibonacci_elementE(10000, 2089)" | |
], | |
"execution_count": null, | |
"outputs": [ | |
{ | |
"output_type": "execute_result", | |
"data": { | |
"text/plain": [ | |
"mpf('33644764876439916400815769589976078277491540121598258624968783032187393983272937480220981902421945505330411162204414862352539419893003230331211469105401819891464280931134789935010847082585417743397526537902805522516533878186308781596146011340513775346991228053661448198598751876535328889029120717497623929300246924400514970993768341462774994775768254846513002338877459453421149271615086279909221234553101677564170630050075245955519692502470738742379660856991066444206258808165652165135646622725572875663091902612272309931585516277475992594254193979017208096055803131937054956327964259681718821919839211299122369393992723073707267009019658577479713801227041638652656240330045949819420085971413007319627039581069899355886242076537925173531308834414999675251591358241183087502881505881044448277686014027101584484227633952346775935272858283007651161334683673909916296744232726220769302789400937707277496846580860627987841856477238200468779655463932740655857836750418244098472020885355509232878913261947040038737564308747597783383591268598241729421837886434406685268775496514359484451202776206326653541834967980593775845121553771544765853133992082721449920757980796959725331026662550083500929961963705413756197892937697200361789487613152732457599977602993970980512390443845336114103542939264948686799655520353918203970524639387471667289674599757320794139351207784612967222392475008953858559208139915414065830092743634769202224124898647431586475503650096231926568930139219606063541759445182284826992725569179564407494267781240823709114267545635717507109657792407983769307760802304728106286780341944909187280433076522059822645758199229178902231338865675005872340333771137208679551422499247187371089829530936820362966568301252767182762280385628471788927478288012469690835955413213338357388554300372467846384674196077057288000850192970641095110654740332234579129669896834554904235967154027963759254997513964371069845494650160128247992801902412125314906147247138185035198232086551203407976797819733468415774753321065220137591530492020962251008082510982814892002572343846610765309535613337532106561735.0')" | |
] | |
}, | |
"metadata": {}, | |
"execution_count": 29 | |
} | |
] | |
} | |
] | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment