演算法簡介

1.分治法(divide and conquer)

   遞迴演算法
   謝耳排序法
   合併排序法
  快速排序法
  基數排序法
  二分搜尋法
  內插搜尋法


2.遞迴法(recursion)
  階乘函數
  費伯那序列
  堆疊
  河內塔
  二元樹走訪
  先深後廣走訪法
  先廣後深走訪法

3.貪心法(greed method)
   最小花費擴張樹
   圖形最短路徑法


4.動態規劃法(dynamic programing algorithom)
   改良版費伯那序列


5.枚舉法
   回溯法
   列出某一範圍間5的倍數
   選擇排序法
   循序搜尋法


6.回溯法(backtracking)
   走鼠走迷宮
   八皇后問題

7.疊代法(iterative method)
   求取最大公因數
   汽泡排序法
   矩陣相加
   矩陣相乘
   轉置矩陣
   鍵結串列

apdapted from 圖說演算法

目錄 檔案2

先找出現在home 的路徑


import os
home=os.path.expanduser("~")
print(home)

==============Q1
開始一個檔案 在home的路徑 建一個檔案 dumu.txt 文字為
 遠上寒山石徑斜，
白雲生處有人家。
停車坐愛楓林晚，
霜葉紅於二月花。

 

import os
home=os.path.expanduser("~")
print(home)
file1=open("/home/up/dumu.txt","a")
file1.write("杜枚 山行")
file1.write("\n遠上寒山石徑斜，")
file1.write("\n白雲生處有人家。")
file1.write("\n停車坐愛楓林晚，")
file1.write("\n霜葉紅於二月花。")
file1.close()

=====================
 Q2:開啟檔案 並讀取檔案

import os
home=os.path.expanduser("~")
print(home)
file2=open("/home/up/dumu.txt","r")
data=file2.readlines()
print(data)
file2.close()


==========
Q3: 列印標題及指標在文件的位址

import os
home=os.path.expanduser("~")
print(home)
file3=open("/home/up/dumu.txt","r")
file3.seek(0) #移動到指定位址
title=file3.read(5) #到指定位址 讀五個字
title_address=file3.tell()
print("標題是{}".format(title))
print("指標在文件的位址是{}".format(title_address))
file3.close()

big o of n

Big o of n ==>演算法的時間複雜度
                 ==>最常用表示理論的上限



時間複雜度的等級  (最下方時間　愈久)

O(1)              常數時間  (constant time)

O(log₂ n)      次線性時間 (sub-linear)

O(n)             線性時間  (linear)

O(n log₂ n)   線性乘對數時間

O(n²)           平方時間  (quadratic)

O(n³)           立方時間  (cubic)

O(2ⁿ)           指數時間   (exponential)

O(n!)           階乘時間   (factorial)


實例  from   
from  https://ithelp.ithome.com.tw/articles/10221991

1.O(1)              常數時間  (constant time)

   陣列讀取

   

   fruits=["apple","banana","cherry","dragonfruit","elderberry","fig"]

   print(fruits[5])


2.O(log₂ n)      次線性時間 (sub-linear)
   二分搜尋法


3.O(n)             線性時間  (linear)
    簡易搜尋
   循序搜尋 (Sequential Search)

fruits=["apple","banana","cherry","dragonfruit","elderberry","fig"]
for i in range(len(fruits)):
    if fruits[i]=="fig":
        print("找到了在{}個裡".format(i+1))
        break
    else:

        print("第{}個裡找不到".format(i+1))


4.O(n log₂ n)   線性乘對數時間
   高級排序算法（合併排序 (Merge sort)、快速排序 (Quick sort)）


5.O(n²)           平方時間  (quadratic)

    簡單排序算法（選擇排序 (Selection sort)、插入排序(Insertion sort)、氣泡排序 (Bubble sort)）


6   O(n³)           立方時間  (cubic)
    Floyd 算法(動態規畫) / 矩陣乘法運算

7.   O(2ⁿ)           指數時間   (exponential)
      河內塔(動態規畫)  簡單背包問題(動態規畫)

8. O(n!)           階乘時間   (factorial)

     旅行推銷員問題 - NP

To sum up

1.binary search
2.selection sort
3. recursion
4.quicksort
5.hash tables
6.breadth first search
7,Dijkra's algorothm
8,greedy algorothm
9.dynamic programming
10.k nearest neighbors

list

array_list=[0]*6
print("最初的list是{}".format(array_list))
for i in range(6):
    array_list[i]=i
    print("第{}+1次的list是{}".format(i,array_list))

廣度優先搜尋(breadth first search)

節點(node)
邊(edge)
有向圖(directed graph)
無向圖(undirected graph)
佇列(queue)  FIFO(first in first out)
堆疊(stack)  FILO (first in last out)

快速排序法(quickSort)二

list 運用

list01=[88,5,3,77,33,22]

less=[i for i in list01 if i<=22]

larger=[j for j in list01 if j>22]

print(less)

print(larger)

==============
def qs(list):
   
    if (len(list)<2):
        return list
    else:
        pivot=list[0]
        less=[i for i in list[1:] if i<=pivot]
        larger=[i for i in list[1:] if i>pivot]
        return qs(less)+[pivot]+qs(larger)
list01=[12,42,245,24,88,77]
print(qs(list01))