%=====================================================================
% ���Ĺ��� 2E ���󹩳س��� �ƥ�����
%�����ơ��ޡ�������4
%    �ܥƥ����Ȥ�����
%        ��
%        ��
%        ��
%        ��
%������ ����
%
% last updated 2005.10.06
%    created by  Masashi Yamamoto
%     e-mail yamamoto@akita-nct.jp
%=====================================================================
\documentclass[10pt,a4paper]{jarticle}
\usepackage{graphicx,amsmath,amssymb,ascmac,float}
\usepackage{html, listings, jlisting}
\oddsidemargin 0mm  %����;�� 25.4mm-0mm������ڡ���
\evensidemargin 0mm %����;�� 25.4mm-0mm�������ڡ���
\textwidth 160mm
\newcommand{\command}[1]{��\texttt{#1}��}
\newcommand{\cl}[1]{\texttt{#1}}
\newcommand{\tw}[1]{\texttt{#1}}
%
\newcounter{toi_num}
\newcommand{\toi}{\textbf{\texttt [��\arabic{toi_num}]}
   \addtocounter{toi_num}{1}}
\newcommand{\qbox}[1]{
    {\fboxsep=2pt\fboxrule=0.4pt\fbox{\hspace{3mm}{#1}\hspace{3mm}}}
}
%
\renewcommand{\lstlistingname}{�ꥹ��}
\lstset{language=C,%
        basicstyle=\footnotesize,%
        commentstyle=\textit,%
        classoffset=1,%
        keywordstyle=\bfseries,%
	frame=tRBl,framesep=5pt,%
	showstringspaces=false,%
        numbers=left,stepnumber=1,numberstyle=\footnotesize%
	}%
%
\begin{htmlonly}
\usepackage{verbatimfiles}
 \providecommand{\lstinputlisting}[2][]{\verbatimlisting{#2}}
\end{htmlonly}
%
\begin{document}
\title{������(����4)}
\author{���ܾ���\thanks{��Ω����ˡ�͡����Ĺ��ȹ�������ع����ŵ����󹩳ز�}}
\date{2005ǯ11��07��}
\maketitle
%
%
%=====================================================================
\section{�����γؽ�����}
%=====================================================================
\begin{itemize}
\item ñ������������
\item 2ʬ����������
\end{itemize}
%
%=====================================================================
\section{ñ������������}
%=====================================================================
�����ˤĤ��Ƥϡ����ʽ��ʬ����䤹��������Ƥ���Τǡ������Ȥä��������롥��������ޤǤ�ʤ������ʽ����ɤ���С�ľ���˸���������Ǥ���Ǥ�������

�׻��̤Υ��������ˤĤ��ơ���ñ���������롥������$i$�ġ����󤬴�λ���ơ�$i+1$���ܤ����󤵤��뤳�Ȥ�ͤ��롥
\begin{itemize}
\item �����$i+1$���ܤ����������٤����֤򸫤Ĥ��뤿�����Ӥ�ʿ�Ѳ��(������)�ϡ�$i/2$�Ǥ��롥
\item ���֤����Ĥ��ä���硤������������뤿��ˡ������ʿ�Ѥ�$i/2$�θ򴹤�ɬ�פǤ��롥
\end{itemize}
���Τ��Ȥ��顤�����$i+1$���ܤ����������֤��������뤿��ˤϡ���碌��$i$��η׻�\footnote{�����Ǥϡ���Ӥ�����θ򴹤�׻��ȸ��äƤ��롥}��ɬ�פȤʤ롥�礭����$N$�ο������ΤǤϡ�
%
\begin{align}
  \sum_{i=1}^{N-1}i&=\frac{(N-1)(N-2)}{2}\nonumber\\
  &=\frac{1}{2}N^2-\frac{3}{2}N+1
\end{align}
%
�Ȥʤ롥$N$���礭����硤$N^2/2$������Ū��$N^2$�����㤷�ơ��׻��̤����ä��롥���Τ褦�ʾ�硤�׻��̤Υ���������ɽ������Ȥ���$O(N^2)$�Ƚ񤯤Τϡ������Ҥ٤��Ȥ���Ǥ��롥
%---------------------------------------------------------------------
\subsection{ñ�����������Ȥ��ͻ�}
%---------------------------------------------------------------------
���ʽ�Υץ������(List 1-7)��Ȥä�����ñ�����������Ȥ��ͻҤ��\ref{fig:simple_sort}�˼����������������ʽ�Ȥϰۤʤꡤ����(����)���礭����$N=20$�Ȥ��Ƥ��롥
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=0.65]
  {figure/simple_sort.eps}
  \caption{ñ�����������Ȥ��ͻҡ�}
  \label{fig:simple_sort}
 \end{center}
\end{figure}
%
%=====================================================================
\section{2ʬ����������}
%=====================================================================
%---------------------------------------------------------------------
\subsection{����}
%---------------------------------------------------------------------
����⡤���ʽ��ʬ����䤹���������񤫤�Ƥ���Τǡ������Ȥä��������롥��������ޤǤ�ʤ������ʽ����ɤ���С������ľ��������Ǥ���Ǥ�������

�׻��̤Υ��������˴ؤ��Ƥϡ����ʽ���������Խ�ʬ�Ǥ��롥��ۤɤ�Ʊ�ͤˡ�������$i$�ġ����󤬴�λ���ơ�$i+1$���ܤ����󤵤��뤳�Ȥ�ͤ��롥
\begin{itemize}
\item �����$n+1$���ܤ����������٤����֤򸫤Ĥ��뤿�����Ӥ�ʿ�Ѳ��(������)�ϡ�$\log_2 i$�Ǥ��롥
\item ���֤����Ĥ��ä���硤������������뤿��ˡ������ʿ�Ѥ�$i/2$�θ򴹤�ɬ�פǤ��롥
\end{itemize}
���Τ��Ȥ��顤�����$i+1$���ܤ����������֤��������뤿��ˤϡ���碌��$i/2+\log_2 i$��η׻���ɬ�פȤʤ롥�礭����$N$�ο������ΤǤϡ�
%
\begin{align}
  \sum_{i=1}^{N-1}\left(\frac{i}{2}+\log_2 i\right)&=\frac{(N-1)(N-2)}{4}+\log_2(N-1)!\nonumber\\  
  &\qquad\text{$N$���礭�����Υ�������󥰤ζ��(} n!\simeq\sqrt{2\pi n}n^n e^{-n} \text{)��Ȥ���}\nonumber \\
  &\simeq\frac{1}{4}N^2-\frac{3}{4}N+\frac{1}{2}+\log_2\left[
  \sqrt{2\pi (n-1)}(n-1)^{(n-1)} e^{-n+1}
  \right]\nonumber \\
  &\simeq\frac{1}{4}N^2-\frac{3}{4}N+\frac{1}{2}
  +\frac{1}{2}\log_2\left[2\pi (n-1)\right]
  +(n-1)\log_2(n-1)
  +(1-n)\log_2 e
\end{align}
%
�Ȥʤ롥$N$���礭����硤$N^2/4$������Ū��$N^2$�����㤷�ơ��׻��̤����ä��롥���äơ��׻��̤Υ��������ϡ�$O(N^2)$�Ǥ��롥

����ޤǤη׻����顤2ʬ���������Ȥϡ�ñ�����������Ȥ���٤ơ�2�����٤�®�٤����äǤ��뤳�Ȥ�ʬ���롥
%
%---------------------------------------------------------------------
\subsection{2ʬ���������Ȥ��ͻ�}
%---------------------------------------------------------------------
���ʽ�Υץ������(List 1-8)��Ȥä�����2ʬ���������Ȥ��ͻҤ��\ref{fig:nibunsonyu_sort}�˼����������������ʽ�Ȥϰۤʤꡤ����(����)���礭����$N=20$�Ȥ��Ƥ��롥
%
\begin{figure}[H]
  \begin{center}
    \includegraphics[keepaspectratio,scale=0.65]
		    {figure/nibunsonyu_sort.eps}
		    \caption{2ʬ���������Ȥ��ͻҡ�}
		    \label{fig:nibunsonyu_sort}
  \end{center}
\end{figure}
%
%=====================================================================
\section{�����ȤΤޤȤ�}
%=====================================================================
����ԥ塼�����Ǥϡ����̤Υǡ������갷�������ξ�硤�ǡ�������§�ɤ�����¤�Ǥ��뤳�Ȥ����פǤ��롥��§�ɤ�����¤�Ǥ���ȡ��ǡ�����õ�����֤�������û�̤Ǥ��롥����ϡ��ʹ֤��޽�ۤǤ��륿���ȥ���ܤ�õ���Ȥ��䡤���¼�ŵ��ñ���Ĵ�٤�Ȥ���Ʊ���Ǥ��롥

��§�ɤ���˥ǡ������¤٤뤳�Ȥ򥽡���(sort)\footnote{�����ƥ��󥰡��¤��ؤ�������դ��ȸ������Ȥ⤢�롥}�Ȥ����������Ǥϡ������Υǡ����򾮤�����(����)���¤٤���ˡ��ؽ������������ǤϽҤ٤ʤ��ä������դ��礭����Τ��Ȥ�߽�ȸ������ֵ��Ǥϡ��ʲ��Υ����ȤˤĤ��Ƴؽ�������
\begin{itemize}
\item �Х֥륽����
  \begin{quote}
    ������٤ɤ��������Ǥ��羮����Ӥ��Ƥ�����򴹤��ʤ��饽���Ȥ�����ˡ�Ǥ��롣�򴹤�1��������ʤ��ä��顤�����Ȥ���λ�Ǥ��롥����ϡ��������ͤΥǡ�����ˢ(�Х֥롨bubble)�Τ褦���⤫��ǹԤ��褦�˸�����\footnote{����˥����Ȥ����硥}���Ȥ��餳��̾�����Ĥ���줿��
  \end{quote}
\item �����å�������
  \begin{quote}
    �����Ĥ����Ǥ���Ȥ�����ͤ���礭�����롼�פȾ��������롼�פ�ʬ���롥ʬ����줿���롼�פ�Ʊ�ͤ���ˡ��ʬ���롥���ƤΥ��롼�פ����Ǥ�1�Ĥˤʤ�ޤǤ��κ�Ȥ򷫤꤫���������ΤȤ������Ȥ���λ���롥���������ʥ����Ȥ���ǡ�ʿ��Ū�ˤϺ�®�Ǥ��뤫�顤����̾�����Ĥ��Ƥ��롥
  \end{quote}
\item �ޡ���������
  \begin{quote}
    �ǽ�˾��ʤ��Ŀ��ο�����¤��ؤ������롼�פ��롥���ˡ�2�ĤΥ��롼�פ�ʻ��(�ޡ���)���ơ�����礭���¤��ؤ���줿���롼�פ��롥����򷫤��֤����Ȥˤ�ꡤ�礭�ʥ��롼�פ��Ǥ����ǽ�Ū�ˤϰ�ĤΥ��롼�פˤʤ��¤��ؤ�����λ���롥
  \end{quote}
\item �����ॽ����
  \begin{quote}
    �Х֥륽���Ȥ��٤Ȥ���ӤΤ��ᡤ�������ͤϰ�Ĥ��Ĥ�����ư�Ǥ��ʤ�(����)����Ӥ���ֳ֤򹭤����ơ��쵤�˰�ư��������ˡ�������ॽ���ȤǤ��롥���Υ����ȤǤϡ�Ŭ���ʴֳ֤ǥХ֥륽���Ȥ�Ԥ������ˤ��δֳ֤򶹤����ˡ���Ȥ��롥�¸����顤�ֳ֤�$1/1.3$���ľ��������Ƥ����Τ��ɤ��ȸ����Ƥ��롥�ǽ�Ū�ˤ��٤Ȥ����(�ֳ֤�1)��Ԥ����򴹤�������ʤ���Х����Ȥδ�λ�Ǥ��롥 
  \end{quote}
\item ñ������������
  \begin{quote}
    �ޤ����ǽ�ο����2�Ĥ���Ӥ��ơ��������ۤ��򺸤ˡ��礭���ۤ��򱦤ˤ��롥���˿����3���ܤ򡤤��κ��ˤ���2�Ĥο���Ⱦ������ۤ���������Ӥ������ޤ���֤�õ�����ơ��������롥�����4����,5���ܡ�$\cdots$�Ƚ缡������κǸ�ޤǷ����֤����Ǹ�ο����������줿�饽���Ȥ���λ�Ǥ��롥
  \end{quote}
\item 2ʬ����������
  \begin{quote}
    ñ�����������ȤǤϡ�����Τ����ͤ���������Ŭ���ʰ��֤�ü������õ���Ƥ���(��˥���������)�����֤�õ��������¤��ؤ����Ƥ���Τǡ�������ͤ�����Ӥ���Х��ʥ꡼����������ǽ�ǡ������Ŭ�Ѥ���®�٤θ����ޤä���ˡ����2ʬ���������ȤǤ��롥
  \end{quote}
\end{itemize}

�����ؽ����������Ȥη׻��̤Ȱ������ˤĤ��Ƥϡ�ɽ\ref{table:sort_characteristic}(���ʽ�� Table 1-2)�ΤȤ���Ǥ��롥
\begin{table}[H]
  \caption{�����ȤΥ��르�ꥺ�����ħ}
  \label{table:sort_characteristic}
  \begin{center}
    \begin{tabular}{lll}
      \hline
      \multicolumn{1}{c}{���르�ꥺ��} &
      \multicolumn{1}{c}{�׻��̥�������} &
      \multicolumn{1}{c}{������} \\
      \hline \hline
      �Х֥륽���� & $O(N^2)$ & ���� \\
      �����å������� &$O(N\log N)$ ��$O(N^2)$ & �԰��� \\
      �ޡ��������� & $O(N\log N)$ & ���� \\
      �����ॽ���� & $O(N\log N)$ & �԰��� \\
      ñ������������ & $O(N^2)$ & ���� \\
      2ʬ���������� & $O(N^2)$ & ���� \\
      \hline
    \end{tabular}
  \end{center}
\end{table}
%=====================================================================
\section{����}
%=====================================================================
%---------------------------------------------------------------------
\subsection{��������}
%---------------------------------------------------------------------
�ʲ��ο���Υ����Ȥ˴ؤ�������Ǥ��롥����򤽤줾��˥����Ȥ��¤��ؤ���Ԥä���
�硤�����ͻҤ򼨤������ιֵ��Ρ��ȤΡ֥����Ȥ��ͻҡפǼ������褦�˵��Ҥ�����ɤ���
���������ͻҤϼ�񤭤ǽ񤯤��ȡ�
%
\begin{quote}
 \begin{small}
  \begin{verbatim}
752 778	608 239 956 244 535 840 629 353 784 199 945 847 637 413 686 172 462 223
  \end{verbatim}
 \end{small}
\end{quote}
%

�������������Ȥ������Ͻ����ֹ�ˤ��ۤʤ롥
%
\begin{itemize}
 \item �����ֹ�β�1�夬1��9�ξ�硤���ο�����10�Ĥο���򥽡��Ȥ��롥���Ȥ��С�
       ����夬3�ξ��ϡ�
%
       \begin{quote}
	\begin{small}
	 \begin{verbatim}
	608 239 956 244 535 840 629 353 784 199
	 \end{verbatim}
	\end{small}
       \end{quote}
�Ǥ��롥
\item �����ֹ�β�1�夬0�ξ�硤����10���ܤ���10�Ĥΰʲ��ο���򥽡��Ȥ��롥
%
       \begin{quote}
	\begin{small}
	 \begin{verbatim}
	353 784 199 945 847 637 413 686 172 462
	 \end{verbatim}
	\end{small}
       \end{quote}
%
\end{itemize}

\setcounter{toi_num}{1}
\begin{quote}
 \begin{itemize}
  \item[\toi]ñ�����������ȤǾ���ξ��
  \item[\toi]2ʬ���������ȤǾ���ξ��
 \end{itemize}
\end{quote}
%---------------------------------------------------------------------
\subsection{��ݡ����������}
%---------------------------------------------------------------------
�����ˡ�ϡ������̤�Ȥ��롣
% 
\begin{quote}
 \begin{tabular}{ll}
  ���� & 11��14��(��) AM 10:40 \\
  �ѻ� & A4 \\
  ��о�� & ���ܸ��漼�������Υݥ��� \\
  ɽ�� & ɽ���1��Ĥ��ơ��ʲ��ι��ܤ�ʬ����䤹�����Ҥ��뤳�ȡ�\\
       & \qquad ���Ȳ���̾�־��󹩳ء�\\
       & \qquad ����̾�ֲ��ꡡ������(����4)��\\
       & \qquad 2E\quad �����ֹ�\quad ��̾\\
       & \qquad �����\\
  ���� & 2�ڡ����ʹߤ��䤤���Ф���������ʬ����䤹�����Ҥ��뤳�ȡ�
 \end{tabular}
\end{quote}
%=====================================================================
\end{document}
