# 1.基础知识1

## 算法设计

* 1.问题建模
* 2.选择什么算法
* 3.算法是否所有实例最优解
* 4.不是，找到反例

## 1.2算法设计的两个例子

### 1.调度问题

> 有n项任务，每项任务加工时间已知，从0时刻开始陆续安排任务到一个机器上加工。
>
> 每个任务完成时间，**都是从0时刻到这个加工任务截止**时间。
>
> 求：总完成时间，最短的方案安排

#### 贪心法

> 按照加工时间排序，小的先加工

![](/files/-Lr8fBd78NBnR-TK3BnC)

证明：

![](/files/-Lr8fBdAI6XnC7B_tD5c)

#### 问题建模

![](/files/-Lr8fBdC0OF3Zj3VyRFG)

#### 反例

经典背包问题

贪心：单位价值越大的先装，但是不一定对

![](/files/-Lr8fBdExH7AbY4v0_4_)

### 2.投资问题

> m元钱，投资n个项目，效益fi(x)，表示第i个项目投x元的效益，i=1,...,n
>
> 如何分配项目，使投资收益最大？

![](/files/-Lr8fBdGJtbaPCq72Dp1)

#### 问题建模

![](/files/-Lr8fBdINHWyx4ribaOK)

解决：穷举，指数时间

![](/files/-Lr8fBdKRXXvr8vOlGsY)

## 1.3算法的设计复杂度

### 排序算法复杂度

![](/files/-Lr8fBdM5dCa-RqYKk5U)

## 1.4货郎问题(NP-hard问题)

### 问题

![](/files/-Lr8fBdOxoR7rtr6U7p2)

### 问题建模

![](/files/-Lr8fBdQIxa2lyahBnS9)

### 解决

目前没有有效的算法解决，只能启发、暴力

### 0.1背包

问题

![](/files/-Lr8fBdSYShbglrZwkT3)

建模

![](/files/-Lr8fBdUO52v2MYFMSEd)

### 双机调度问题

问题

![](/files/-Lr8h0EM5FfSOyJBe5IB)

建模

![](/files/-Lr9Fh0mPwEOdBjcxD9T)

## 1.5 算法及时间复杂度


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/interview/1-1-1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.