python算法

标签：定义   归并   排序   假设   ext   orm   忽略   shuff   app   

引言

定义：算法就是按照一定步骤解决问题的办法

属性：

• 正确：就是可以正确的求解问题
• 快速：就是时间复杂度要尽量小
• 有穷性：要在有限个步骤解决问题

渐进分析法为什么可以做到与算法运行硬件环境无关？

算法分析时往往假设输入规模n足够大,甚至趋近于无穷大。这样的假设,意味着我们关注的是算法运算时间的增长率,也就是,随着输入规模n的增长,T(n)的增长率。当n趋向于无穷大时,决定T(n)增长率的便是T(n)中的高次项,从而可以忽略T(n)中的低次项以及高次项前的常数项。这些低次项或者高次项前的常数项,往往是机器性能、程序设计语言的性能和编译器性能等因素产生,而这些在算法时间复杂度分析中都是需要略去的次要因素。

为什么说多项式时间复杂度的算法要优于指数时间复杂度的算法?

渐进分析与python模型

二分搜索

def binary_search(A,k):
    first=0
    last= len(A)-1 
    found=False
    while first

确界Θ、上界Ο、下界Ω

问题求解和代码优化

递归算法和递归函数

主分析法求时间复杂度

• 当f(n) ,这种情况意味着,递归树上各层结点的和从根结点开始依次递增,由于渐进表示可以去掉低次项,因此得T(n)=Θ(nlogba)。
• 当f(n) = nlogba,k是大于等于0的常数。这种情况意味着,递归树上各层结点的和从根结点开始并没有显著变化,因此得 T(n)=Θ( nlogba*logn)
• 当f(n) > nlogba,同时对于常数c

给定正整数N,计算所有长度为N但没有连续1的二分字符。比如,N=2时,输

出为[00,01,10]:当N=3时,输出为1000,001,010,100,101。

import math

N = int(input("输入N:"))

def ss(a):
    a = bin(a)[2:]
    j = 6
    for i in a:
        if j == i == '1':
            return False
        j = i
    return True

def printN(a, N):
    a = bin(i)[2:]
    while len(a) 

统计逆序数问题

#_*_coding:UTF-8_*_

import random


#逆序计算的简单算法
def count_inversions_simple(A):
    inv_count = 0
    inv_list = []
    for i in range(len(A)):
        for j in range(i, len(A)):
            if A[i] > A[j]:
                inv_count += 1
                inv_list.append([A[i],A[j]])
    return inv_count, inv_list


#逆序计算的分治算法   边排序边找逆序数
#类似归并排序，加入了逆序数计算 T(n) = 2T(n/2) + O(n) = O(nlogn)
def count_inversions_dc(A):
    if len(A)  B[j] 则B[j]与A右边所有元素构成逆序
            inv_count += len(A) - i
            alist.append(B[j])
            j += 1
    while i 

第k小的数

方法一（课本）：

#_*_coding:utf-8_*_

import random

def select_fct(array, k):
    if len(array)  0:
        num_medians += 1
    for i in range(num_medians):
        beg = i * subset_size
        end = min(len(array), beg+subset_size)
        subset = array[beg:end]
        subsets.append(subset)
    medians = []
    for subset in subsets:
        median = select_fct(subset, len(subset)//2)
        medians.append(median)
    pivot = select_fct(medians, len(subset)//2)
    return pivot

def patition_array(array, pivot):
    array_lt = []
    array_gt = []
    array_eq = []
    for item in array:
        if item  pivot:
            array_gt.append(item)
        else:
            array_eq.append(item)
    return array_lt, array_gt, array_eq


def main():
    num = 20
    array = [random.randint(1,100) for x in range(num)]
    random.shuffle(array)         #random.shuffle(x[, random])：用于将一个列表中的元素打乱
    random.shuffle(array)
    k = 7
    print(sorted(array))
    kval = select_fct(array, k)
    print("第八小："+str(kval))
    sorted_array = sorted(array)
    assert sorted_array[k] == kval    #python assert断言是声明其布尔值必须为真的判定，如果发生异常就说明表达示为假。
    
if __name__ == '__main__':
    main()

方法二：

#_*_coding:utf-8_*_
#分治法解决第k小的数
import random

def partition(nums):
    pi = nums[0]
    low = [x for x in nums[1:] if x = pi]
    return low, pi, high

# 查找第 k 小的元素
def solve(nums, k):
    low, pi,high = partition(nums)    #分解
    n = len(low) 
    if n+1 == k:    #k+1表示第k小
        return pi
    elif n 

硬币找零，贪心算法

#零钱找零,pay是应付金额
def coin(pay):
    m = [100, 25, 10, 5, 1]
    list = []

    sort_m = sorted(m, reverse=True)
    for i in sort_m:
        coin_count = int(pay/i)
        list += [i,] * coin_count
        pay -= coin_count*i
        if pay 

digkstra算法求单源最短路径

#_*_coding:utf-8_*_
#单源最短路径问题

MAX_value = 999999

def dijkstra(graph, s):  #s是源点，d(s) = 0
    if graph is None:    # 判断图是否为空，如果为空直接退出
        return None
    dist = [MAX_value,]*len(graph)
    dist[s] = 0
    S = []
    Q = [i for i in range(len(graph))]
    dist_init = [i for i in graph[s]]
    while Q:
        u_dist = min([d for v, d in enumerate(dist_init) if v in Q])
        u = dist_init.index(u_dist)
        S.append(u)
        Q.remove(u)
 
        for v, d in enumerate(graph[u]):
            if 0  dist[u]+d:
                    dist[v] = dist[u]+d
                    dist_init[v] = dist[v]
                    print(dist[v])
    return dist    #到每一个点的最短路径距离
 
 
if __name__ == '__main__':
    graph_list = [  [0, 9, MAX_value, MAX_value, MAX_value, 14, 15, MAX_value],
                    [9, 0, 24, MAX_value, MAX_value, MAX_value,MAX_value,MAX_value],
                    [MAX_value, 24, 0, 6, 2, 18,MAX_value,19],
                    [MAX_value, MAX_value, 6, 0, 11,MAX_value,MAX_value, 6],
                    [MAX_value,MAX_value, 2, 11, 0, 30,20, 16],
                    [14,MAX_value,18,MAX_value,30,0,5,MAX_value],
                    [15,MAX_value,MAX_value,MAX_value,20,5,0,44],
                    [MAX_value,MAX_value,19,6,16,MAX_value,44,0]]
 
    distance = dijkstra(graph_list, 0)
    print(distance)  

动态规划问题

#_*_coding:utf-8_*_
#动态规划
import numpy as np 
import random

#斐波那契函数
memo = {}   #字典
def fib2(n):
    if n in memo:
        return memo[n]
    else:
        if n = 1:
        if table[i] > table[i-1]:
            select.append(row_coins[i-1])
            i -= 2
        else:
            i -= 1
    return select



#子序列和的最大值
def num_max(alist):    #自底向上递归
    table = [None] * (len(alist)+1)      
    table[0] = 0
    for i in range(1, len(alist)+1):
        table[i] = max(table[i-1] + alist[i-1], alist[i-1])  #计算重新开始的优劣
    return table

def tract_back_subseq(alist, table):
    select = []
    ind_max = np.argmax(table)        #得到最大值索引
    while ind_max >= 1:
        if table[ind_max] == alist[ind_max-1] + table[ind_max-1]:
            select.append(alist[ind_max-1])
            ind_max -= 1
        else:
            select.append(alist[ind_max-1])
            break
    return select


if __name__ == "__main__":
    list = [random.randint(1,20) for x in range(10)]
    print(list)
    print(fib2(10))
    print(fib_bottom_up(10))

    table = bottom_up_coins(list)
    print(trace_back_coins(list, table))

    table = num_max(list)
    print(tract_back_subseq(list, table))
    

0,1 背包问题

#_*_coding:utf-8_*_
#0 1 背包问题
#分析： k(i, x) = max(k(i-1, x), k(i-1, x-s) + v) 物品i放入背包，不放入背包

def knapSack(W, wt, val, n):
    #W是容量， wt是物品容量，val是价值， n是物品数量
    k = [[0 for x in range(W+1)] for x in range(n+1)]
    for i in range(n+1):
        for w in range(W+1):
            if i == 0 or w == 0:     #不满足条件，物品或者容量为空
                k[i][w] = 0
            elif wt[i-1] 

python算法

标签：定义   归并   排序   假设   ext   orm   忽略   shuff   app   

原文地址：https://www.cnblogs.com/tomyyyyy/p/11125793.html