19th Ave New York, NY 95822, USA

# 数学代考| Elements of Complexity Theory 复杂度理论代写

my-assignmentexpert愿做同学们坚强的后盾，助同学们顺利完成学业，同学们如果在学业上遇到任何问题，请联系my-assignmentexpert™，我们随时为您服务！

## 运筹学代写

Complexity theory is arguably the foundation for analysis of computer algorithms. The goal of the theory is twofold: to develop criteria for measuring the effectiveness of various algorithms (and thus, be able to compare algorithms using these criteria), and to assess the inherent difficulty of various problems.

The term complexity refers to the amount of resources required by a computation. In this chapter we focus on a particular resource, namely, computing time. In complexity theory, however, one is not interested in the execution time of a program implemented in a particular programming language, running on a particular computer over a particular input. This involves too many contingent factors. requirements.
Roughly speaking, to do so one needs to define:

• a notion of input size,
• a set of basic operations, and
• a cost for each basic operation.
The last two allow one to associate a cost of a computation. If $x$ is any input, the cost $C(x)$ of the computation with input $x$ is the sum of the costs of all the basic operations performed during this computation.
Let $\mathcal{A}$ be an algorithm and $\mathcal{J}{n}$ be the set of all its inputs having size $n$. The worst-case cost function of $\mathcal{A}$ is the function $T{\mathscr{A}}^{w}$ defined by
$$T_{\mathcal{A}}^{w}(n)=\sup {x \in \mathcal{I}{n}} C(x) .$$
If there is a probability structure on $\mathcal{J}{n}$ it is possible to define the average-case cost function $T{\mathscr{A}}^{a}$ given by
$$T_{\mathcal{A}^{a}}(n)=\mathrm{E}{n}(C(x))$$ where $\mathrm{E}{n}$ is the expectation over $\mathcal{J}_{n}$. However, the average is usually more difficult to find, and there is of course the issue of what probabilities to assign.

We now discuss how the objects in the three items above are selected. The selection of a set of basic operations is generally easy. For the algorithms we consider in this chapter, the obvious choice is the set ${+,-, \times, /, \leq}$ of the four arithmetic operations and the comparison. Selecting a notion of input size and a cost for the basic operations depends on the kind of data dealt with by the algorithm. require a variable amount.

Examples of the first are fixed-precision floating-point numbers, stored in a fixed amount of memory (usually 32 or 64 bits). For this kind of data the size of an element is usually taken to be 1 and consequently to have unit size per number.
132
5 Interior-Point Methods
Examples of the second are integer numbers which require a number of bits approximately equal to the logarithm of their absolute value. This (base 2) logarithm is usually referred to as the bit-size of the integer. Similar ideas apply for rational numbers.

Let $A$ be some kind of data and $\mathbf{x}=\left(x_{1}, \ldots, x_{n}\right) \in A^{n}$. If $A$ is of the first kind above then we define $\operatorname{size}(\mathbf{x})=n$. Otherwise, we define $\operatorname{size}(\mathbf{x})=\sum_{i=1}^{n}$ bit-size $\left(x_{i}\right)$.
The cost of operating on two unit size numbers is taken to be 1 and is called the unit cost. In the bit-size case, the cost of operating on two numbers is the product of their bit-sizes (for multiplications and divisions) or their maximum (for additions, subtractions, and comparisons).

The consideration of integer or rational data with their associated bit-size and bit cost for the arithmetic operations is usually referred to as the Turing model of computation. The consideration of idealized reals with unit size and unit cost is today referred as the real number arithmetic model. When comparing algorithms, one should

A basic concept related to both models of computation is that of polynomial time.
A basic concept related to both models of computation is that of polynomial time. An algorithm $\mathcal{A}$ is said to be a polynomial time algorithm if $T_{\mathcal{A}}(n)$ is bounded above by a polynomial. A problem can be solved in polynomial time if there is a polynomial time algorithm solving the problem.
is defined similarly, replacing $T_{\mathcal{A}}$ by $T_{\mathscr{A}}^{a}$. The notion of polynomial time is usually taken as the formalization of efficiency in complexity theory.

## Elements of Complexity Theory复杂度理论代写

• 输入大小的概念，
• 一组基本操作，以及
• 每个基本操作的成本。
最后两个允许将计算成本关联起来。如果 $x$ 是任何输入，则输入 $x$ 的计算成本 $C(x)$ 是在此计算期间执行的所有基本操作的成本总和。
令 $\mathcal{A}$ 是一个算法，$\mathcal{J}{n}$ 是它所有大小为 $n$ 的输入的集合。 $\mathcal{A}$ 的最坏情况成本函数是由下式定义的函数 $T{\mathscr{A}}^{w}$
$$T_{\mathcal{A}}^{w}(n)=\sup {x \in \mathcal{I}{n}} C(x) 。$$
如果 $\mathcal{J}{n}$ 上存在概率结构，则可以定义平均情况成本函数 $T{\mathscr{A}}^{a}$
$$T_{\mathcal{A}^{a}}(n)=\mathrm{E}{n}(C(x))$$ 其中 $\mathrm{E}{n}$ 是对 $\mathcal{J}_{n}$ 的期望。然而，平均值通常更难找到，当然还有分配什么概率的问题。

132
5 内点法

## 什么是运筹学代写

• 确定需要解决的问题。
• 围绕问题构建一个类似于现实世界和变量的模型。
• 使用模型得出问题的解决方案。
• 在模型上测试每个解决方案并分析其成功。
• 实施解决实际问题的方法。

## 运筹学代写的三个特点

• 优化——运筹学的目的是在给定的条件下达到某一机器或者模型的最佳性能。优化还涉及比较不同选项和缩小潜在最佳选项的范围。
• 模拟—— 这涉及构建模型，以便在应用解决方案刀具体的复杂大规模问题之前之前尝试和测试简单模型的解决方案。
• 概率和统计——这包括使用数学算法和数据挖掘来发现有用的信息和潜在的风险，做出有效的预测并测试可能的解决方法。