作業場所が小さいマージソートと計算量の評価
スポンサーリンク
概要
- 論文の詳細を見る
マージソートは時間計算量がO (n log n) (nはソートされるレコードの個数) であり高速であるが, 内部ソートとして実行する場合, 作業場所として大きさnの配列を要するのが欠点であるとされている. 本論文では, 作業場所として数語だけを要するマージソートを提案する. 新しいマージソートの時間計算量はO (n log^2 n) であり, 従来のアルゴリズムより悪いが, これは作業場所とのトレードオフの結果である.
- 1999-05-10
著者
-
萩原 洋一
東京農工大学総合情報メディアセンター
-
中森 眞理雄
東京農工大学大学院共生科学技術研究部
-
池田 諭
東京農工大学工学部情報コミュニケーション工学科
-
中森 眞理雄
東京農工大学
-
萩原 洋一
東京農工大学
-
中森 眞理雄
東京農工大 大学院共生科学技術研究院
-
中森 眞理雄
東京農工大学 工学府情報工学専攻
-
中森 真理雄
東京農工大学工学部数理情報工学科
-
池田 諭
東京農工大学工学部
-
池田 諭
東京農工大・工
-
萩原 洋一
東京農工大学総合情報処理センター
関連論文
- (48) 情報系専門学科のカリキュラムのアイデンティティと評価方法(第4セッション 教育評価方法)
- PDAを利用した監視画像検索システムの構築
- B-7-73 IPIDを用いた連続転送パケット解析によるトラヒック特性評価(B-7.情報ネットワーク,一般講演)
- Mac OS XによるNetbootを用いた端末室環境の運用 (第12回学術情報処理研究集会)
- 気象データサーバシステムの構築と運用(分散システム構築運用技術,ユーザ指向の分散システム/インターネットの運用・管理)
- 半導体露光装置におけるディストーション調整の最適化(機械力学,計測,自動制御)
- 選択グラフの性質とフローショップスケジューリング問題(アルゴリズム一般)
- 困難な問題の双線形計画問題を用いたモデル化手法
- 論理式充足可能性,整数計画,および双線形計画について
- 実環境下における分散型センサネットワークの提案(UBI-3【センサネットワーク/実世界センシング】)
- 作業場所が小さいマージソートと計算量の評価
- 作業領域が小さいマージソート
- トランスポジショングラフにおける素な経路
- 大学における女性卒業生支援を目的としたソーシャル・ネットワーキング・サービスの提案と実践
- 女性の再チャレンジ支援を目的としたSNSの構築
- 実環境下における分散型センサネットワークの提案(UBI-3【センサネットワーク/実世界センシング】)
- 排他的論理和を含む論理式に対する充足可能性問題
- 特集「情報教育〜理論・評価・発展〜」の編集にあたって
- 資源と作業順序の制約を拡張したスケジューリング問題に対する下界値の計算法
- XMLを用いた遠隔機器制御支援システムとDBMSやICカードの連携(情報家電と組込みシステム)
- 大学ネットワーク機器更新のための消費電力の簡易測定
- 情報工学系学科における実験・演習の一設計例
- TCP 通信に対するパッシブ測定による RTT 推定法の一考察(インターネットの新しいサービスとその基盤技術及び一般)
- 基板生産における生産ラインのラインバランシング問題に対するヒューリスティックな解法
- 基板生産における生産ラインのラインバランシング問題に対するヒューリスティックな解法
- 基板生産における生産ラインのラインバランシング問題に対するヒューリスティックな解法
- 基板生産時における部品装着機の部品吸着順序問題に対する近似解法(セッション4)
- 基板生産時における部品装着機の部品配置問題および部品吸着順序問題のモデル化と解法
- 部品装着機における部品供給部への部品割当問題および部品吸着順序問題に対する解法(スケジューリング)
- 基板生産時における部品装着機の部品配置問題および部品吸着順序問題のモデル化と解法
- 変形均衡割当て問題- 2次元ベクトルの場合 -
- ネットワークカメラを用いた監視システムの拡張(分散システム構築運用技術,ユーザ指向の分散システム/インターネットの運用・管理)
- 3層チャネル配線における平面配線可能な最大ネット集合の選択手法
- WWWによるアルゴリズム研究支援環境
- アルゴリズムベースのためのグラフアルゴリズムの部品化
- 電子メールのオブジェクト指向データベースによる管理方法の提案
- 対象の代数構造を重視したアルゴリズム記述法
- 音楽ライブラリデータベースの設計と実装
- 情報工学系学科の教育における手回し計算器の活用
- ドットマトリクスの回転等に関する算法に対する書換え規則のなす群について
- 関係データベースシステムにおける画像情報操作機能
- 方形チップ格子上のウェーハ配置最適化(VLSI設計技術とCAD)
- 方形チップ格子上のウェーハ配置最適化
- 取得チップ数を最大化するウエハ配置(ケース・スタディ)
- 資源制約と先行制約を拡張したプロジェクトスケジューリング問題とその下界値の計算方法(研究速報)
- NCS(ネットワークカメラシステム)による監視システムの構築と運用(システム構築・運用技術, オープンソース時代の分散システム/インターネットの構築・運用技術)
- Web カメラと携帯電話を連携した監視カメラシステムの構築と運用
- [チュートリアル講演]局所情報を用いる有限グラフ上の乱歩のヒッティング時間とカバー時間
- 局所情報を利用するグラフ上のランダムウオークのカバータイムについて
- 監視カメラ画像閲覧のための階層的画像集約手法
- フローの多重化により生じるバーストパケットの特定方式とトラヒック特性評価(デモ,ポスターセッション,VPN, NAT,ネットワークセキュリティ,DDoS, P2P及び一般)
- ナップザック問題の分枝限定アルゴリズムのランダム化とその解析
- アルゴリズム研究支援環境のためのデータモデルに関する考察
- アルゴリズムの研究支援システムの試作
- オブジェクト指向データベースの電子メールへの適用
- 遺伝的アルゴリズムによる工場設置問題の解法
- L-004 キャンパスネットワーク更新前の消費電力の簡易測定(L分野:ネットワーク・セキュリティ,一般論文)
- 多地点接続遠隔講義システムのための予約システムの構築と問題点
- 2G-7 全国18国立大学法人を結ぶHD対応遠隔講義システムの展開(教育方法・教育システム,一般セッション,コンピュータと人間社会)
- 全国18国立大学法人を結ぶHD対応遠隔講義システムの設計(パラレル,インターネットと情報倫理教育,一般)
- 全国18国立大学法人を結ぶHD対応遠隔講義システムの設計(パラレル,インターネットと情報倫理教育,一般)
- 全国18国立大学法人を結ぶHD対応遠隔講義システムの設計(パラレル,インターネットと情報倫理教育,一般)
- 全国18国立大学高精細遠隔講義システムの設計構築と課題
- 日本の授業形式を考慮した新板書管理システムの設計
- N_011 DVTSを用いた多地点遠隔講義支援教室の構築(N分野:教育・人文科学)
- LL-005 ICカードによる認証システムの構築法(L分野:ネットワークコンピューティング)
- ハッチングパターンを用いた多属性気象データの可視化(セッション4:分析と可視化,テーマ:CGと記録及びCG一般)
- 7)放送衛星波の小口径アンテナによる受信CN比の年間特性について(無線・光伝送研究会)
- 放送衛星波の小口径アンテナによる受信CN比の年間特性について
- 27-1 BSにおける雨、露によるCN比変動について
- ネットワークを流れるバーストパケットの特定方式とトラヒック特性評価
- IPIDを用いたバーストパケット特定方式とトラヒック特性評価(トラヒック,一般)
- サーバの負荷を考慮したSACKの性能評価の一考察(トラヒック, 一般)
- パッシブ/アクティブ検知を用いたP2Pトラヒック特定法
- B-6-79 各種TCPバージョンの実測定によるトラヒック特性の評価(B-6. ネットワークシステム, 通信2)
- 確率的なグラフ連結性判定アルゴリズム
- メモリ領域が小さい確率的なグラフ連結性判定アルゴリズムについて
- ネットワークセキュリティ総合監査とその評価
- 静止衛星回線に見られる太陽雑音妨害
- 航空機散乱波によるテレビ受信電界のモデル計算
- WWW上におけるアルゴリズムアニメーションシステムの構築
- WWW上におけるアルゴリズムアニメーションシステムの構築
- ピュアP2P型アプリケーショントラヒック特定法とトラヒック特性解析(トラヒック,一般)
- Hausdorff測度とpacking測度が同等となるフラクタル集合のあるクラスについて
- 3D-12 障害物のある場合の警備員経路問題に関する研究
- 障害物のある警備員経路問題に関する研究
- 12)衛星放送受信に見られる太陽雑音妨害によるC/N特性(無線・光伝送研究会)
- 衛星放送受信に見られる太陽雑音妨害によるC/N特性
- 11)放送衛星のCN比と気象現象について(無線・光伝送研究会)
- 放送衛星のCN比と気象現象について
- B-7-116 複数のキャンパスネットワークを統合するバックボーンにおけるトラヒックの解析と特性評価(B-7. 情報ネットワーク)
- キャンパスネットワークの省電力化と管理省力化の取り組み(運用管理・支援2,インターネットと情報倫理教育,一般)
- キャンパスネットワークの省電力化と管理省力化の取り組み(運用管理・支援2,インターネットと情報倫理教育,一般)
- 衛星放送受信に見られる太陽雑音妨害によるC/N特性
- シンクライアントと持ち込みノートPCによる端末室デスクトップ環境の設計(サービス管理,運用管理技術,セキュリティ管理,及び一般)
- シラバスシステムと連携した講義支援システム
- 複数キャンパスの電力の見える化と電力制限の前後の計測 (情報通信マネジメント)
- IP電話端末を利用した在席表示システムの構築と運用 (コンシューマ・デバイス&システム Vo.2 No.2)
- 複数キャンパスの電力の見える化と電力制限の前後の計測(サービス管理,運用管理技術,セキュリティ管理,及び一般)
- 大学における女性卒業生支援を目的としたソーシャル・ネットワーキング・サービスの提案と実践