Java版算法珠玑

  • 更新时间:
  • 8478人关注
  • 点击下载

这是一个不错的Java算法类学习资源,由冷元化提供,主要知识点是关于Java算法珠玑、算法珠玑、Java算法的内容,已被281人关注,同类资源中评分为7.3分。

本书的目标读者是准备去硅谷找工作的码农,也适用于在国内找工作的码农,以及刚接触ACM算法竞赛 的新手。

本书有如下特色:

背后有强大的AlgoHub支持。

本书的所有题目,都可以在www.algohub.org上在线判断代码。这样的一大好处是,读者可以边看书,边实现自己的代码,然后提交到网站上验证自己的想法是否正确。 AlgoHub的使命是成为最好的算法学习和交流平台。AlgoHub囊括了POJ, ZOJ, leetcode, HackerRank 等网站的经典题目(一些质量不高的题目则忽略),且 AlgoHub有非常简单的加 题系统,用户不需要写一行代码即可自己添加题目,所以AlgoHub的题库还在飞速增长中。

每道题都有完整的代码。

市场上的大部分书,都会讲思路,但给出的代码都是片段,不是完整可编译的代码。本书每题都 有完整的代码,且每个代码经过千锤百炼,保证可读性的前提下尽可能简短,方面读者在面试中 能快速写出来。

每道题都有多种解法。

本书的宗旨是,用尽可能少的题目,覆盖尽可能多的算法。本书中的的每道题都有多种解法,每 种解法不是简单的小改进,而是完全不同的思路,力求举一反三,让读者触类旁通。

本书支持多种主流编程语言

目前支持 Java, C++, C#, Python, Ruby, JavaScript, Swift, Scala, Clojure, 将来还会支持更多编程语言。

精选笔记:使用java写的矩阵乘法实例(Strassen算法)

16小时35分钟前回答

Strassen算法于1969年由德国数学家Strassen提出,该方法引入七个中间变量,每个中间变量都只需要进行一次乘法运算。而朴素算法却需要进行8次乘法运算。

原理

Strassen算法的原理如下所示,使用sympy验证Strassen算法的正确性

import sympy as s
 
A = s.Symbol("A")
B = s.Symbol("B")
C = s.Symbol("C")
D = s.Symbol("D")
E = s.Symbol("E")
F = s.Symbol("F")
G = s.Symbol("G")
H = s.Symbol("H")
p1 = A * (F - H)
p2 = (A + B) * H
p3 = (C + D) * E
p4 = D * (G - E)
p5 = (A + D) * (E + H)
p6 = (B - D) * (G + H)
p7 = (A - C) * (E + F)
 
print(A * E + B * G, (p5 + p4 - p2 + p6).simplify())
print(A * F + B * H, (p1 + p2).simplify())
print(C * E + D * G, (p3 + p4).simplify())
print(C * F + D * H, (p1 + p5 - p3 - p7).simplify())

复杂度分析

$$f(N)=7\times f(\frac{N}{2})=7^2\times f(\frac{N}{4})=...=7^k\times f(\frac{N}{2^k})$$

最终复杂度为$7^{log_2 N}=N^{log_2 7}$

java矩阵乘法(Strassen算法)

代码如下,可以看看数据结构的定义,时间换空间。

public class Matrix {
	private final Matrix[] _matrixArray;
	private final int n;
	private int element;
	public Matrix(int n) {
		this.n = n;
		if (n != 1) {
			this._matrixArray = new Matrix[4];
			for (int i = 0; i < 4; i++) {
				this._matrixArray[i] = new Matrix(n / 2);
			}
		} else {
			this._matrixArray = null; 
		}
	}
	private Matrix(int n, boolean needInit) {
		this.n = n;
		if (n != 1) {
			this._matrixArray = new Matrix[4];
		} else {
			this._matrixArray = null; 
		}
	}
	public void set(int i, int j, int a) {
		if (n == 1) {
			element = a;
		} else {
			int size = n / 2;
			this._matrixArray[(i / size) * 2 + (j / size)].set(i % size, j % size, a);
		}
	}
	public Matrix multi(Matrix m) {
		Matrix result = null;
		if (n == 1) {
			result = new Matrix(1);
			result.set(0, 0, (element * m.element));
		} else {
			result = new Matrix(n, false);
			result._matrixArray[0] = P5(m).add(P4(m)).minus(P2(m)).add(P6(m));
			result._matrixArray[1] = P1(m).add(P2(m));
			result._matrixArray[2] = P3(m).add(P4(m));
			result._matrixArray[3] = P5(m).add(P1(m)).minus(P3(m)).minus(P7(m));
		}
		return result;
	}
	public Matrix add(Matrix m) {
		Matrix result = null;
		if (n == 1) {
			result = new Matrix(1);
			result.set(0, 0, (element + m.element));
		} else {
			result = new Matrix(n, false);
			result._matrixArray[0] = this._matrixArray[0].add(m._matrixArray[0]);
			result._matrixArray[1] = this._matrixArray[1].add(m._matrixArray[1]);
			result._matrixArray[2] = this._matrixArray[2].add(m._matrixArray[2]);
			result._matrixArray[3] = this._matrixArray[3].add(m._matrixArray[3]);;
		}
		return result;
	}
	public Matrix minus(Matrix m) {
		Matrix result = null;
		if (n == 1) {
			result = new Matrix(1);
			result.set(0, 0, (element - m.element));
		} else {
			result = new Matrix(n, false);
			result._matrixArray[0] = this._matrixArray[0].minus(m._matrixArray[0]);
			result._matrixArray[1] = this._matrixArray[1].minus(m._matrixArray[1]);
			result._matrixArray[2] = this._matrixArray[2].minus(m._matrixArray[2]);
			result._matrixArray[3] = this._matrixArray[3].minus(m._matrixArray[3]);;
		}
		return result;
	}
	protected Matrix P1(Matrix m) {
		return _matrixArray[0].multi(m._matrixArray[1]).minus(_matrixArray[0].multi(m._matrixArray[3]));
	}
	protected Matrix P2(Matrix m) {
		return _matrixArray[0].multi(m._matrixArray[3]).add(_matrixArray[1].multi(m._matrixArray[3]));
	}
	protected Matrix P3(Matrix m) {
		return _matrixArray[2].multi(m._matrixArray[0]).add(_matrixArray[3].multi(m._matrixArray[0]));
	}
	protected Matrix P4(Matrix m) {
		return _matrixArray[3].multi(m._matrixArray[2]).minus(_matrixArray[3].multi(m._matrixArray[0]));
	}
	protected Matrix P5(Matrix m) {
		return (_matrixArray[0].add(_matrixArray[3])).multi(m._matrixArray[0].add(m._matrixArray[3]));
	}
	protected Matrix P6(Matrix m) {
		return (_matrixArray[1].minus(_matrixArray[3])).multi(m._matrixArray[2].add(m._matrixArray[3]));
	}
	protected Matrix P7(Matrix m) {
		return (_matrixArray[0].minus(_matrixArray[2])).multi(m._matrixArray[0].add(m._matrixArray[1]));
	}
	public int get(int i, int j) {
		if (n == 1) {
			return element;
		} else {
			int size = n / 2;
			return this._matrixArray[(i / size) * 2 + (j / size)].get(i % size, j % size);
		}
	}
	public void display() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				System.out.print(get(i, j));
				System.out.print(" ");
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		Matrix m = new Matrix(2);
		Matrix n = new Matrix(2);
		m.set(0, 0, 1);
		m.set(0, 1, 3);
		m.set(1, 0, 5);
		m.set(1, 1, 7);
		n.set(0, 0, 8);
		n.set(0, 1, 4);
		n.set(1, 0, 6);
		n.set(1, 1, 2);
		Matrix res = m.multi(n);
		res.display();
	}
 
}

总结

到此这篇关于使用java写的矩阵乘法的文章就介绍到这了,更多相关java矩阵乘法(Strassen算法)内容请搜索码农之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持码农之家!

相关声明:

Java版算法珠玑下载资源由用户 向颖初 于 2021-10-01 08:08:53 分享至百度网盘。仅供想学习Java算法的网友交流使用,专题参考:Java算法,

相关资源

  • 数据结构与算法Java语言描述

    数据结构与算法Java语言描述

    编辑推荐 如果你是一名正在学习计算机科学的学生,或者你是一个正在准备技术面试的软件开发者,本书将以一种更清晰、更具体,以及更吸引人的方式帮助你学习并回顾软件工程中*重要的部分-----数据结构和算法。 内容简介 本书作者强调实践知识和技能胜过理论,在书中为你展示了怎样使用数据结构实现有效的算法,并分析和测试了算法的性能。在本书中你将探索Java集合框架(JCF)中重要的类,它们是如何实现的,以及如何执行。书中的每一章都提

    大小:147 MB数据结构

    立即下载
  • 深入Java虚拟机:JVM G1GC的算法与实现

    深入Java虚拟机:JVM G1GC的算法与实现

    编辑推荐 结合实用JVM,图解Java垃圾回收机制的关键技术! 90张图表+33段代码,轻松理解G1GC算法原理 HotSpotVM源码剖析,深入探讨G1GC具体实现 1.深入Java虚拟机底层原理,详细解读经典GC算法; 2.理论结合实际,基于HotSpotVM源码探讨具体实现; 3.图文并茂、深入浅出,辅以大量插图和代码细致讲解。 内容简介 本书深入Java虚拟机底层原理,对JVM内存管理中的垃圾回收算法G1GC进行了详细解读。全书分为算法篇和实现篇两大部分:前一部分主要介绍G1GC的算法

    大小:129 MBJava虚拟机

    立即下载
  • 学习JavaScript数据结构与算法(第3版)

    学习JavaScript数据结构与算法(第3版)

    大小:13.6 MBJavaScript

    立即下载

学习笔记

3小时58分钟前回答

基于JavaScript实现的快速排序算法分析

本文实例讲述了基于JavaScript实现的快速排序算法。分享给大家供大家参考,具体如下: 首先要介绍一下 冒泡排序 ,冒泡排序的过程很简单, 首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个关键字交换,然后比较第二个和第三个,直到最后一个比较完成。这是第一趟冒泡,其结果使得关键字最大的记录被安置到最后一个位置上了。然后对序列前n-1个元素进行第二次冒泡,将倒数第二个选出。以此类推直到所有被选出,冒泡结束 。 通过分析可以得出,冒泡排序的时间复杂度为 O(n2) 。 快速排序是对冒泡排序的一种改进,它是处理大数据集最快的排序之一, 通过递归……