小编Har*_*son的帖子

我正在学习如何使用cmake这个类,但文档非常冗长和密集.许多教程要么太简单而无法使用(仅使用一个文件进行cmake)或太复杂.

该项目的原始Makefile如下所示:

# Some optimization settings
# see: http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

# Standard all target
all: hw1_p2

# Simple program to do brute-force k-nearest neighbor searches against a signature file
hw1_p2: prob2.o ParseRecord.o Sorter.o Timing.o
        g++ -o hw1_p2 prob2.o ParseRecord.o Sorter.o Timing.o

prob2.o: prob2.cpp utility_templates.hpp
        g++ -Wall -c prob2.cpp

ParseRecord.o: ParseRecord.cpp ParseRecord.hpp utility_templates.hpp
        g++ -Wall -c ParseRecord.cpp

Sorter.o: Sorter.cpp Sorter.hpp
        g++ -Wall -c Sorter.cpp

# Timing class
Timing.o: Timing.hpp Timing.cpp
        g++ -Wall -c Timing.cpp

# Clean code-derived files
clean:
        rm -f *.o …

我正在通过CLRS进行算法简介练习.这不是分级作业或任何东西,我只是想了解问题.

问题如下:

我们可以将插入排序表达为递归过程,如下所示.为了对A [1..n]进行排序,我们递归地对A [1..n-1]进行排序,然后将A [n]插入到排序的数组A [1..n-1]中.写一个递归版本的插入排序的运行时间的重复.

解决问题的方法:

由于在最坏的情况下花费O(n)时间将A [n]插入到排序的数组A [1中..n -1],如果n = 1则得到递归T(n)= O(1),如果n> 1则得到T(n-1)+ O(n).该复发的解决方案是T(n)= O(n ^ 2).

所以如果n = 1那么我得到它,那么它已经被排序,因此需要O(1)时间.但是我不理解重复的第二部分:O(n)部分是我们将被排序的元素插入到数组中的步骤,该数组在最坏的情况下采用O(n)时间 - 我们必须的情况遍历整个数组并在其末尾插入.

我无法理解它的递归部分(T(n-1)).T(n-1)是否意味着每个递归调用我们正在排序一个较少的数组元素？这似乎不对.

如果有数据类型

data Arith  = Con Int
              | Add Arith Arith
              | Sub Arith Arith
              | Mul Arith Arith
              | Div Arith Arith

一个实例:

instance Show Arith where
    show (Con i)     = show i
    show (Add e1 e2) =  "(" ++ show e1 ++ " + " ++ show e2 ++ ")" 
    show (Sub e1 e2) =  "(" ++ show e1 ++ " - " ++ show e2 ++ ")" 
    show (Mul e1 e2) =  "(" ++ show e1 ++ " …